{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost to Make All Characters Equal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使所有字符相等的最小成本"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的二进制字符串 <code>s</code> ，你可以对其执行两种操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选中一个下标 <code>i</code> 并且反转从下标 <code>0</code> 到下标 <code>i</code>（包括下标 <code>0</code> 和下标 <code>i</code> ）的所有字符，成本为 <code>i + 1</code> 。</li>\n",
    "\t<li>选中一个下标 <code>i</code> 并且反转从下标 <code>i</code> 到下标 <code>n - 1</code>（包括下标 <code>i</code> 和下标 <code>n - 1</code> ）的所有字符，成本为 <code>n - i</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回使字符串内所有字符 <strong>相等</strong> 需要的 <strong>最小成本</strong> 。</p>\n",
    "\n",
    "<p><strong>反转</strong> 字符意味着：如果原来的值是 '0' ，则反转后值变为 '1' ，反之亦然。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"0011\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>执行第二种操作，选中下标 <code>i = 2</code> ，可以得到 <code>s = \"0000\" ，成本为 2</code> 。可以证明 2 是使所有字符相等的最小成本。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"010101\"\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>执行第一种操作，选中下标 i = 2 ，可以得到 s = \"101101\" ，成本为 3 。\n",
    "执行第一种操作，选中下标 i = 1 ，可以得到 s = \"011101\" ，成本为 2 。\n",
    "执行第一种操作，选中下标 i = 0 ，可以得到 s = \"111101\" ，成本为 1 。\n",
    "执行第二种操作，选中下标 i = 4 ，可以得到 s = \"111110\" ，成本为 2 。\n",
    "执行第一种操作，选中下标 i = 5 ，可以得到 s = \"111111\" ，成本为 1 。\n",
    "使所有字符相等的总成本等于 9 。可以证明 9 是使所有字符相等的最小成本。 </pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length == n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code> 为 <code>'0'</code> 或 <code>'1'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-to-make-all-characters-equal](https://leetcode.cn/problems/minimum-cost-to-make-all-characters-equal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-to-make-all-characters-equal](https://leetcode.cn/problems/minimum-cost-to-make-all-characters-equal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"0011\"', '\"010101\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        t = tuple(target)\n",
    "        dis = defaultdict(lambda: inf)\n",
    "        dis[tuple(start)] = 0\n",
    "        vis = set()\n",
    "        while True:\n",
    "            v, dv = None, -1\n",
    "            for p, d in dis.items():\n",
    "                if p not in vis and (dv < 0 or d < dv):\n",
    "                    v, dv = p, d\n",
    "            if v == t: return dv  # 到终点的最短路已确定\n",
    "            vis.add(v)\n",
    "            vx, vy = v\n",
    "            dis[t] = min(dis[t], dv + t[0] - vx + t[1] - vy)  # 更新到终点的最短路\n",
    "            for x1, y1, x2, y2, cost in specialRoads:\n",
    "                w = (x2, y2)\n",
    "                dis[w] = min(dis[w], dv + abs(x1 - vx) + abs(y1 - vy) + cost, dv + abs(x2 - vx) + abs(y2 - vy))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        start = tuple(start)\n",
    "        target = tuple(target)\n",
    "        dist = defaultdict(lambda:float('inf'))\n",
    "        dist[start] = 0\n",
    "        visited = set()\n",
    "        cur = start\n",
    "        while True:\n",
    "            if cur == target:\n",
    "                print(dist)\n",
    "                return dist[cur]\n",
    "\n",
    "            visited.add(cur)#加入visited\n",
    "\n",
    "            x,y = cur\n",
    "            dist[target] = min(dist[target], dist[cur]+abs( target[0] - x) + abs(target[1]-y))  # 更新到终点的最短路\n",
    "\n",
    "            # 遍历所有边\n",
    "            for x1,y1,x2,y2,w in specialRoads:\n",
    "                # t1 = (x1,y1)\n",
    "                # if t1 not in dist:\n",
    "                #     dist[t1] = dist[cur]+abs(x1-x)+abs(y1-y)\n",
    "                t2 = (x2,y2) #一条线段看作一个点\n",
    "                dist[t2] = min(dist[t2],dist[cur]+abs(x1-x)+abs(y1-y)+w) \n",
    "                # dist[t2] = min(dist[t2],dist[t1]+w)\n",
    "\n",
    "\n",
    "            minw = float('inf')\n",
    "            for k,v in dist.items():\n",
    "                if v < minw and k not in visited:\n",
    "                    cur = k\n",
    "                    minw = v\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: list[int], target: list[int], specialRoads: list[list[int]]) -> int:\n",
    "        nodes = set([tuple(start), tuple(target)])\n",
    "        cost = collections.defaultdict(int)\n",
    "\n",
    "        for x1, y1, x2, y2, c in specialRoads:\n",
    "            if (x1, y1, x2, y2) not in cost:\n",
    "                cost[(x1, y1, x2, y2)] = c\n",
    "            else:\n",
    "                cost[(x1, y1, x2, y2)] = min(cost[(x1, y1, x2, y2)], c)\n",
    "            nodes.add((x1, y1))\n",
    "            nodes.add((x2, y2))\n",
    "\n",
    "        minHeap = [(0, start[0], start[1])]\n",
    "        visited = set()\n",
    "        minCost = {node: float('inf') for node in nodes}\n",
    "        minCost[(start[0], start[1])] = 0\n",
    "\n",
    "        while minHeap:\n",
    "            c, x, y = heapq.heappop(minHeap)\n",
    "            if (x, y) in visited:\n",
    "                continue\n",
    "            visited.add((x, y))\n",
    "\n",
    "            for nx, ny in nodes:\n",
    "                if (nx, ny) not in visited:\n",
    "                    sc = cost[(x, y, nx, ny)] if (x, y, nx, ny) in cost else float('inf')\n",
    "                    nc = min(sc, abs(nx-x)+abs(ny-y)) + c\n",
    "                    if nc < minCost[(nx, ny)]:\n",
    "                        minCost[(nx, ny)] = nc\n",
    "                        heapq.heappush(minHeap, (nc, nx, ny))\n",
    "\n",
    "        return minCost[(target[0], target[1])]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        def m(x1,y1,x2,y2):\n",
    "            return abs(x2-x1) + abs(y2-y1)\n",
    "        \n",
    "        sx, sy = start\n",
    "        tx, ty = target\n",
    "        \n",
    "        sr = specialRoads\n",
    "        # sr = []\n",
    "        # for x1,y1,x2,y2,cost in specialRoads:\n",
    "        #     # if cost > m(x1,y1,x2,y2): continue\n",
    "        #     sr.append([x1,y1,x2,y2,cost])\n",
    "        \n",
    "        # if len(sr) == 0:\n",
    "        #     return m(sx,sy,tx,ty)\n",
    "        \n",
    "        q = [(0, sx, sy)] \n",
    "        # dist = [inf] * len(specialRoads) \n",
    "        dist = defaultdict(lambda: inf)\n",
    "        vis = set()\n",
    "        ans = inf\n",
    "        while q:\n",
    "            d, sx, sy = heappop(q)\n",
    "            if dist[(sx,sy)] < d:\n",
    "                continue\n",
    "            if (sx,sy) in vis:\n",
    "                continue\n",
    "            vis.add((sx,sy)) \n",
    "            ans = min(ans, m(sx,sy,tx,ty) + d)\n",
    "            for x1,y1,x2,y2,c in sr:\n",
    "                d3 = d + m(sx,sy,x1,y1) + c\n",
    "                # print(f'{x2,y2},{dist[(x2,y2)]}')\n",
    "                if d3 <= dist[(x2,y2)]:\n",
    "                    dist[(x2,y2)] = d3\n",
    "                    heappush(q, (d3, x2, y2))\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        start, target = tuple(start), tuple(target)\n",
    "        dis = defaultdict(lambda :inf)\n",
    "        dis[start] = 0\n",
    "        pq = [(0, start)]\n",
    "        visited = defaultdict(bool)\n",
    "        # visited[tuple(start)] = True\n",
    "        while pq:\n",
    "            # 此时到u为最短路径\n",
    "            dis_u, u = heapq.heappop(pq)\n",
    "            if u == target or dis_u >= dis[target]:\n",
    "                return dis[target]\n",
    "            if visited[u]:\n",
    "                continue\n",
    "\n",
    "            visited[u] = True\n",
    "            # 更新一下target：start-> u -> target\n",
    "            dis[target] = min(dis[target], dis_u+target[0]-u[0]+target[1]-u[1])\n",
    "            for x1, y1, x2, y2, cost in specialRoads:\n",
    "                v = (x2, y2)\n",
    "                # 更新一下v: start-> u -> (x1, y1) -> v\n",
    "                # 可以发现，v从没更新过 start->v这条路径\n",
    "                # 这是因为 更新到所有特殊路径的终点的最短路：要么走曼哈顿距离直接过去，要么先走曼哈顿距离到特殊路径的起点，再走特殊路径。这两者取最小值。但实际上只需要考虑走特殊路径的情况，连续的曼哈顿走法可以合并成一个曼哈顿走法。\n",
    "                dis[v] = min(dis[v], dis_u + abs(x1-u[0]) + abs(y1-u[1])+cost)\n",
    "                heapq.heappush(pq, (dis[v], v))\n",
    "        \n",
    "        return dis[target]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        def cost(start, target):\n",
    "            sx, sy = start\n",
    "            tx, ty = target\n",
    "            return abs(tx-sx)+abs(ty-sy)\n",
    "                \n",
    "        h = [(0,start[0],start[1],-1),]\n",
    "        target = tuple(target)\n",
    "        visited_nodes = set()\n",
    "        unvisited_roads = set(range(len(specialRoads)))\n",
    "\n",
    "        while h:\n",
    "            c,x,y,r = heapq.heappop(h)\n",
    "            if (x,y) == target: return c\n",
    "            if (x,y) in visited_nodes: continue\n",
    "            visited_nodes.add((x,y))\n",
    "            if r in unvisited_roads: unvisited_roads.remove(r)\n",
    "            heapq.heappush(h,(c+cost((x,y),target),target[0],target[1],r))\n",
    "            for i in unvisited_roads:\n",
    "                sx,sy,tx,ty,ci = specialRoads[i]\n",
    "                if (tx,ty) in visited_nodes: continue\n",
    "                heapq.heappush(h,(c+ci+cost((x,y),(sx,sy)),tx,ty,i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        pq = [(0, *start)]\n",
    "        vis = set()\n",
    "        while pq:\n",
    "            dist, x, y = heappop(pq)\n",
    "            if [x, y] == target: return dist\n",
    "            if (x, y) in vis: continue\n",
    "            vis.add((x, y))\n",
    "            for x1, y1, x2, y2, w in specialRoads:\n",
    "                if (x2, y2) not in vis:\n",
    "                    d = min(abs(x - x2) + abs(y - y2), abs(x - x1) + abs(y - y1) + w)\n",
    "                    heappush(pq, (dist + d, x2, y2))\n",
    "            heappush(pq, (dist + abs(x - target[0]) + abs(y - target[1]), *target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(\n",
    "        self, start: List[int], target: List[int], specialRoads: List[List[int]]\n",
    "    ) -> int:\n",
    "        def dist(x1: int, y1: int, x2: int, y2: int) -> int:\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "\n",
    "        q = [(0, start[0], start[1])]\n",
    "        vis = set()\n",
    "        ans = inf\n",
    "        while q:\n",
    "            d, x, y = heappop(q)\n",
    "            if (x, y) in vis:\n",
    "                continue\n",
    "            vis.add((x, y))\n",
    "            ans = min(ans, d + dist(x, y, *target))\n",
    "            for x1, y1, x2, y2, cost in specialRoads:\n",
    "                heappush(q, (d + dist(x, y, x1, y1) + cost, x2, y2))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        ans = 10 ** 18\n",
    "        s = set()\n",
    "        q = [(0, start[0], start[1])]\n",
    "        while q:\n",
    "            dis, x, y = heapq.heappop(q)\n",
    "            if (x, y) in s:\n",
    "                continue\n",
    "            s.add((x, y))\n",
    "\n",
    "            ans = min(ans, dis + abs(x - target[0]) + abs(y - target[1]))\n",
    "            for sx, sy, dx, dy, cost in specialRoads:\n",
    "                heapq.heappush(q, (dis + abs(x - sx) + abs(y - sy) + cost, dx, dy))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "\n",
    "        def calD(s, e):\n",
    "            s1, s2 = s\n",
    "            e1, e2 = e\n",
    "            return abs(s1 - e1) + abs(s2 - e2)\n",
    "\n",
    "        start, target = tuple(start), tuple(target)\n",
    "        edges = []\n",
    "        for a, b, c, d, e in specialRoads:\n",
    "            if calD((a, b), (c, d)) > e:\n",
    "                edges.append((a, b, c, d, e))\n",
    "        \n",
    "        pq = [(0, start)]\n",
    "        seen = set()\n",
    "        while pq:\n",
    "            td, u = heapq.heappop(pq)\n",
    "            if u in seen:\n",
    "                continue\n",
    "            if u == target:\n",
    "                return td\n",
    "            seen.add(u)\n",
    "            for a, b, c, d, e in edges:\n",
    "                nd = td + calD(u, (a, b)) + e\n",
    "                heapq.heappush(pq, (nd, (c, d)))\n",
    "            nd = td + calD(u, target)\n",
    "            heapq.heappush(pq, (nd, target))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        def getDistance(x1, y1, x2, y2):\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "        # 二叉堆优化 Dijkstra 算法\n",
    "        distance = [(0, tuple(start))]\n",
    "        visited = set()\n",
    "        while True:\n",
    "            # 找到距离起点最近的点集邻居顶点\n",
    "            d, (x, y) = heapq.heappop(distance)\n",
    "            while (x, y) in visited:\n",
    "                d, (x, y) = heapq.heappop(distance)\n",
    "            if (x, y) == tuple(target):\n",
    "                return d\n",
    "            # 将该点加入点集，并更新点集邻居与起点的距离\n",
    "            visited.add((x, y))\n",
    "            for x1, y1, x2, y2, cost in specialRoads:\n",
    "                # 使用特殊路径到达出口\n",
    "                if (x, y) == (x1, y1) and (x2, y2) not in visited:\n",
    "                    heapq.heappush(distance, (d + cost, (x2, y2)))\n",
    "                # 到所有特殊路径的入口\n",
    "                elif (x1, y1) not in visited:\n",
    "                    heapq.heappush(distance, (d + getDistance(x, y, x1, y1), (x1, y1)))\n",
    "                # 直接到达终点\n",
    "            heapq.heappush(distance, (d + getDistance(x, y, *target), tuple(target)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        nodes = [start]\n",
    "        m_map = {tuple(start): 0}\n",
    "        for x1, y1, x2, y2, c in specialRoads:\n",
    "            if (x1, y1) not in m_map:\n",
    "                m_map[(x1, y1)] = len(nodes)\n",
    "                nodes.append([x1, y1])\n",
    "            if (x2, y2) not in m_map:\n",
    "                m_map[(x2, y2)] = len(nodes)\n",
    "                nodes.append([x2, y2])\n",
    "        if tuple(target) not in m_map:\n",
    "            m_map[tuple(target)] = len(nodes)\n",
    "            nodes.append(tuple(target))\n",
    "        \n",
    "        n = len(nodes)\n",
    "        dist = [[inf] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dist[i][i] = 0\n",
    "            for j in range(i+1, n):\n",
    "                dist[i][j] = dist[j][i] = abs(nodes[j][0]-nodes[i][0]) + abs(nodes[j][1]-nodes[i][1])\n",
    "\n",
    "        for x1, y1, x2, y2, c in specialRoads:\n",
    "            i = m_map[(x1, y1)]\n",
    "            j = m_map[(x2, y2)]\n",
    "            dist[i][j] = min(dist[i][j], c)\n",
    "        #print(f'{nodes=}')\n",
    "        #print(f'{dist=}\\n{m_map=}')\n",
    "        u, nv = m_map[tuple(start)], m_map[tuple(target)]\n",
    "        dd = [inf] * n \n",
    "        visited = {u,}\n",
    "        dd[u] = 0\n",
    "        while u >= 0:\n",
    "            if u == nv:\n",
    "                return dd[u]\n",
    "            for v in range(n):\n",
    "                if v != u:\n",
    "                    dd[v] = min(dd[v], dd[u] + dist[u][v])\n",
    "            #print(f'{u=} {dd=}')\n",
    "            min_dist = min([dd[i] for i in range(n) if i not in visited], default=-1)\n",
    "            if min_dist == -1:\n",
    "                return -1\n",
    "            idx = next(i for i in range(n) if i not in visited and dd[i] == min_dist)\n",
    "            u = idx\n",
    "            visited.add(u)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        f = lambda p, q: abs(p[0] - q[0]) + abs(p[1] - q[1])\n",
    "        s = {tuple(r) for r in specialRoads if r[4] < f(r, r[2:4])}\n",
    "        m = f(start, target)\n",
    "        h = [(f(start, r), r) for r in s]\n",
    "        heapify(h)\n",
    "        while h:\n",
    "            k, r = heappop(h)\n",
    "            if m <= k:\n",
    "                return m\n",
    "            b, t = k + r[4], r[2:4]\n",
    "            m = min(m, b + f(t, target))\n",
    "            s.discard(r)\n",
    "            for r in s:\n",
    "                heappush(h, (b + f(t, r), r))\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        inf = 10 ** 9\n",
    "        def getDistance(x1, y1, x2, y2):\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "        inf = 10 ** 9\n",
    "        # 建立带权有向图的邻接表\n",
    "        num_special = len(specialRoads)\n",
    "        num_nodes = num_special * 2 + 2\n",
    "        graph = [[] for _ in range(num_nodes)]\n",
    "        for i in range(num_special):\n",
    "            _, _, ux2, uy2, ucost = specialRoads[i]\n",
    "            graph[i].append((num_special + i, ucost))\n",
    "            graph[num_special + i].append((num_nodes - 1, getDistance(ux2, uy2, *target)))\n",
    "            for j in range(num_special):\n",
    "                vx1, vy1, _, _, _ = specialRoads[j]\n",
    "                graph[num_special + i].append((j, getDistance(ux2, uy2, vx1, vy1)))\n",
    "        for i, (x1, y1, _, _, _) in enumerate(specialRoads):\n",
    "            graph[-2].append((i, getDistance(*start, x1, y1)))\n",
    "        graph[-2].append((num_nodes - 1, getDistance(*start, *target)))\n",
    "        # 朴素 Dijkstra 算法\n",
    "        distance = collections.defaultdict(lambda: inf)\n",
    "        distance[num_nodes - 2] = 0\n",
    "        visited = [False] * num_nodes\n",
    "        while True:\n",
    "            # 找到距离起点最近的点集邻居顶点\n",
    "            u = -1\n",
    "            for i in range(num_nodes):\n",
    "                if not visited[i] and (u < 0 or distance[i] < distance[u]):\n",
    "                    u = i\n",
    "            if u == num_nodes - 1:\n",
    "                return distance[u]\n",
    "            # 将该点加入点集，并更新点集邻居与起点的距离\n",
    "            visited[u] = True\n",
    "            for v, w in graph[u]:\n",
    "                distance[v] = min(distance[v], distance[u] + w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        \n",
    "        def dijkstra() :\n",
    "            h = []\n",
    "            sx,sy = start\n",
    "            ex,ey = target\n",
    "            st = [False] * len(specialRoads)\n",
    "            heappush(h,(abs(ey - sy) + abs(ex - sx),ex,ey,-1))\n",
    "            for i,(x1,y1,x2,y2,d) in enumerate(specialRoads) :\n",
    "                heappush(h,(abs(y1 - sy) + abs(x1 - sx) + d,x2,y2,i))\n",
    "            \n",
    "            while h :\n",
    "                dist,x,y,i = heappop(h)\n",
    "                if x == ex and y == ey :\n",
    "                    return dist\n",
    "                if st[i] :\n",
    "                    continue\n",
    "                st[i] = True\n",
    "                for i,(x1,y1,x2,y2,d) in enumerate(specialRoads) :\n",
    "                    heappush(h,(abs(y1 - y) + abs(x1 - x) + d + dist,x2,y2,i))\n",
    "                heappush(h,(abs(ey - y) + abs(ex - x) + dist,ex,ey,-1))\n",
    "            \n",
    "        \n",
    "        return dijkstra()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "\n",
    "        import heapq as hq\n",
    "        from collections import defaultdict\n",
    "\n",
    "        HamitonDis = lambda n1, n2: abs(n1[0]-n2[0])+abs(n1[1]-n2[1])\n",
    "\n",
    "        start, target = (start[0], start[1]), (target[0], target[1])\n",
    "        nodeSet = set()\n",
    "        nodeSet.add(target)\n",
    "\n",
    "        # filter unnecessary special road\n",
    "        newSpecialRoads = defaultdict(dict)\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            if cost < abs(x1-x2) + abs(y1-y2):\n",
    "                newSpecialRoads[(x1, y1)][(x2, y2)] = min(cost, newSpecialRoads.get((x1, y1), {}).get((x2, y2), float(\"inf\")))\n",
    "                nodeSet.add((x1, y1))\n",
    "                nodeSet.add((x2, y2))\n",
    "        \n",
    "        visited = set()\n",
    "        heap = [(0, start)]\n",
    "        while heap:\n",
    "            cost, node = hq.heappop(heap)\n",
    "            if node == target:\n",
    "                return cost\n",
    "            if node in visited:\n",
    "                continue\n",
    "            visited.add(node)\n",
    "            for nextNode in nodeSet:\n",
    "                if nextNode not in visited:\n",
    "                    weight = min(HamitonDis(node, nextNode), newSpecialRoads[node].get(nextNode, float(\"inf\")))\n",
    "                    hq.heappush(heap, (cost+weight, nextNode))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        g = defaultdict(lambda: defaultdict(lambda: inf))\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            g[(start[0], start[1])][(x1, y1)] = min(abs(x1-start[0])+abs(y1-start[1]), g[(start[0], start[1])][(x1, y1)])\n",
    "            g[(x1, y1)][(x2,y2)] =  min(abs(x2-x1)+abs(y2-y1), cost, g[(x1, y1)][(x2,y2)])\n",
    "            g[(x2, y2)][(target[0], target[1])] = min(abs(target[0]-x2)+abs(target[1]-y2), g[(x2, y2)][(target[0], target[1])])\n",
    "        for i in range(len(specialRoads)):\n",
    "            for j in range(len(specialRoads)):\n",
    "                if(i==j): continue\n",
    "                x1, y1, _, _, _ = specialRoads[i]\n",
    "                _, _, x2, y2, _ = specialRoads[j]\n",
    "                g[(x2, y2)][(x1, y1)] = min(g[(x2, y2)][(x1, y1)], abs(x2-x1)+abs(y2-y1))\n",
    "        g[(start[0], start[1])][(target[0], target[1])] = min(g[(start[0], start[1])][(target[0], target[1])], \\\n",
    "            abs(start[0]-target[0]) + abs(start[1]-target[1]))\n",
    "        dis = defaultdict(lambda:inf)\n",
    "        dis[(start[0], start[1])] = 0\n",
    "        vis = set()\n",
    "        n = len(g)\n",
    "        for i in range(n):\n",
    "            x = None\n",
    "            for j in g.keys():\n",
    "                if(j not in vis and (x is None or dis[j] < dis[x])):   #* 如果没有被标记过且当前的最短路, 那么就用x来更新其他点\n",
    "                    x = j\n",
    "            vis.add(x)\n",
    "            for y, w in g[x].items():\n",
    "                if(dis[y] > dis[x] + w):\n",
    "                    dis[y] = dis[x] + w\n",
    "        return dis[(target[0], target[1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(lambda: float('inf'))\n",
    "        res = [[0, (start[0], start[1])]]\n",
    "        target = tuple(target)\n",
    "\n",
    "        while res:\n",
    "            dis, xy = heapq.heappop(res)\n",
    "            if xy == target:\n",
    "                return dis\n",
    "            if dis >= cnt[xy]:\n",
    "                continue\n",
    "            cnt[xy] = dis\n",
    "            x, y = xy\n",
    "            for x1,y1,x2,y2,c in specialRoads:\n",
    "                a = (x2, y2)\n",
    "                b = cnt[xy] + min(abs(x-x1) + abs(y-y1) + c, abs(x-x2) + abs(y-y2))\n",
    "                heapq.heappush(res, [b, a])\n",
    "            x1, y1 = target[0], target[1]\n",
    "            d = cnt[xy] + abs(x-x1) + abs(y-y1)\n",
    "            heapq.heappush(res, [d, (x1,y1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 10**5 \n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "\n",
    "        order = dict()\n",
    "        idx = 0\n",
    "        points=[] \n",
    "\n",
    "        def add(x,y):\n",
    "            if x*MX +y in order:\n",
    "                return\n",
    "            nonlocal idx\n",
    "\n",
    "            order[x*MX+y] = idx\n",
    "            idx+=1\n",
    "            points.append((x,y))\n",
    "\n",
    "        add(start[0],start[1])\n",
    "        add(target[0],target[1])\n",
    "\n",
    "        for x1,y1,x2,y2,cost in specialRoads:\n",
    "            add(x1,y1)\n",
    "            add(x2,y2)\n",
    "\n",
    "        n = idx\n",
    "\n",
    "        dis= [[0]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j:\n",
    "                    dis[i][j] = abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1])\n",
    "\n",
    "        for x1,y1,x2,y2,cost in specialRoads:\n",
    "            i = order[x1*MX+y1]\n",
    "            j = order[x2*MX+y2]\n",
    "            dis[i][j] = min(dis[i][j],cost)\n",
    "\n",
    "        q =deque()\n",
    "\n",
    "        s, t = order[start[0]*MX+start[1]], order[target[0]*MX+target[1]]\n",
    "        vis = [False]*n\n",
    "        dist=[inf]*n\n",
    "        q.append(s)\n",
    "        dist[0]=0\n",
    "\n",
    "        while  q:\n",
    "            x = q.popleft()\n",
    "            # print(x)\n",
    "            for y in range(n):\n",
    "                if x!=y and dist[y] > dist[x]+dis[x][y]:\n",
    "                    dist[y] = dist[x]+dis[x][y]\n",
    "                    q.append(y)\n",
    "\n",
    "        return dist[t]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        print(dis)\n",
    "        return 0\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        shortcut, nodes = dict(), set()\n",
    "        for a,b,c,d,e in specialRoads:\n",
    "            if e >= abs(a-c)+abs(b-d):\n",
    "                continue\n",
    "            if (a,b,c,d) not in shortcut:\n",
    "                shortcut[(a,b,c,d)] = e\n",
    "            else:\n",
    "                shortcut[(a,b,c,d)] = min(e, shortcut[(a,b,c,d)])\n",
    "            nodes.add((a,b))\n",
    "            nodes.add((c,d))\n",
    "        if not shortcut:\n",
    "            return abs(start[0]-target[0]) + abs(start[1]-target[1])\n",
    "        \n",
    "        nodes.add(tuple(start))\n",
    "        nodes.add(tuple(target))\n",
    "\n",
    "        edge = dict()\n",
    "        for s in nodes:\n",
    "            if s not in edge:\n",
    "                edge[s] = dict()\n",
    "            for e in nodes:\n",
    "                if s+e in shortcut:\n",
    "                    edge[s][e] = shortcut[s+e]\n",
    "                else:\n",
    "                    edge[s][e] = abs(s[0]-e[0]) + abs(s[1]-e[1])\n",
    "\n",
    "        shortest = {tuple(start):0}\n",
    "        nodes.remove(tuple(start))\n",
    "        while nodes:\n",
    "            tmp = None\n",
    "            tmp_length = float(\"inf\")\n",
    "            for s in shortest.keys():\n",
    "                for e, road in edge[s].items():\n",
    "                    if e in shortest:\n",
    "                        continue\n",
    "                    if road + shortest[s] < tmp_length:\n",
    "                        tmp_length = road + shortest[s]\n",
    "                        tmp = e\n",
    "            nodes.remove(tmp)\n",
    "            shortest[tmp] = tmp_length\n",
    "            # print(shortest)\n",
    "        return shortest[tuple(target)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        g = collections.defaultdict(list)\n",
    "        n = len(specialRoads)\n",
    "        start = tuple(start)\n",
    "        target = tuple(target)\n",
    "        \n",
    "        def calD(s, e):\n",
    "            s1, s2 = s\n",
    "            e1, e2 = e\n",
    "            return abs(s1 - e1) + abs(s2 - e2)\n",
    "        \n",
    "        g[start].append((target, calD(start, target)))\n",
    "\n",
    "        for i in range(n):\n",
    "            a, b, c, d, cost = specialRoads[i]\n",
    "            g[start].append(((c, d), calD(start, (a, b)) + cost))\n",
    "            g[c, d].append((target, calD((c, d), target)))\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                a1, a2, a3, a4, a5 = specialRoads[i]\n",
    "                b1, b2, b3, b4, b5 = specialRoads[j]\n",
    "                g[a3, a4].append(((b3, b4), calD((a3, a4), (b1, b2)) + b5))\n",
    "\n",
    "        dist = collections.defaultdict(lambda: float(\"inf\"))\n",
    "        seen = set()\n",
    "        dist[start] = 0\n",
    "        pq = [(0, start)]\n",
    "        while pq:\n",
    "            tc, u = heapq.heappop(pq)\n",
    "            if u in seen:\n",
    "                continue\n",
    "            seen.add(u)\n",
    "            for v, nc in g[u]:\n",
    "                if dist[v] > dist[u] + nc:\n",
    "                    dist[v] = dist[u] + nc\n",
    "                    heapq.heappush(pq, (dist[v], v))\n",
    "                    \n",
    "        return dist[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        g = collections.defaultdict(list)\n",
    "        n = len(specialRoads)\n",
    "        start = tuple(start)\n",
    "        target = tuple(target)\n",
    "        \n",
    "        def calD(s, e):\n",
    "            s1, s2 = s\n",
    "            e1, e2 = e\n",
    "            return abs(s1 - e1) + abs(s2 - e2)\n",
    "        \n",
    "        g[start].append((target, calD(start, target)))\n",
    "\n",
    "        for i in range(n):\n",
    "            a, b, c, d, cost = specialRoads[i]\n",
    "            g[start].append(((c, d), calD(start, (a, b)) + cost))\n",
    "            g[(c, d)].append((target, calD((c, d), target)))\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                a1, a2, a3, a4, a5 = specialRoads[i]\n",
    "                b1, b2, b3, b4, b5 = specialRoads[j]\n",
    "                g[(a3, a4)].append(((b3, b4), calD((a3, a4), (b1, b2)) + b5))\n",
    "\n",
    "        dist = collections.defaultdict(lambda: float(\"inf\"))\n",
    "        seen = set()\n",
    "        dist[start] = 0\n",
    "        pq = [(0, start)]\n",
    "        while pq:\n",
    "            tc, u = heapq.heappop(pq)\n",
    "            if u in seen:\n",
    "                continue\n",
    "            seen.add(u)\n",
    "            for v, nc in g[u]:\n",
    "                if dist[v] > dist[u] + nc:\n",
    "                    dist[v] = dist[u] + nc\n",
    "                    heapq.heappush(pq, (dist[v], v))\n",
    "                    \n",
    "        return dist[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        # 每一步的终点必须是target或者specialRoads的起点和终点\n",
    "        ends = {tuple(target)}\n",
    "        road = defaultdict(dict)\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            road[(x1, y1)][(x2, y2)] = min(road[(x1, y1)].get((x2, y2), maxsize), cost)\n",
    "            ends |= {(x1, y1), (x2, y2)}\n",
    "        ends = list(ends)\n",
    "\n",
    "        dist = {}  # start到各点的最短距离\n",
    "        h = [(0, *start)]\n",
    "        while h:\n",
    "            d, i, j = heappop(h)\n",
    "            if [i, j] == target:\n",
    "                return d\n",
    "            if d >= dist.get((i, j), maxsize):\n",
    "                continue\n",
    "            dist[(i, j)] = d\n",
    "\n",
    "            for ii, jj in ends:\n",
    "                temp = min(abs(ii - i) + abs(jj - j), road[(i, j)].get((ii, jj), maxsize))\n",
    "                if d + temp < dist.get((ii, jj), maxsize):\n",
    "                    heappush(h, (d + temp, ii, jj))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        start = tuple(start)\n",
    "        target = tuple(target)\n",
    "        \n",
    "        def get_cost(s,t):\n",
    "            a,b = s\n",
    "            c,d = t\n",
    "            return abs(a-c) + abs(b-d)\n",
    "            \n",
    "        \n",
    "        graph = defaultdict(list)\n",
    "        graph[start].append([target, get_cost(start, target)])\n",
    "        \n",
    "        for a,b,c,d,v in specialRoads:\n",
    "            graph[start].append( [(a,b),  get_cost(start, (a,b))]   )\n",
    "            graph[(a,b)].append( [(c,d), v] )\n",
    "            graph[(c,d)].append( [target, get_cost((c,d), target)]   )\n",
    "            \n",
    "        \n",
    "        n = len(specialRoads)\n",
    "        for i in range(n):\n",
    "            a,b = specialRoads[i][2:4]\n",
    "            for j in range(n):\n",
    "                c,d = specialRoads[j][:2]\n",
    "                graph[(a,b)].append( [(c,d), get_cost( (a,b), (c,d) )] )\n",
    "                \n",
    "            \n",
    "        # spfs\n",
    "        distance = {start:0}\n",
    "        Q = deque([start])\n",
    "        seen = {start}\n",
    "        \n",
    "        while len(Q):\n",
    "            p = Q.popleft()\n",
    "            seen.remove(p)\n",
    "            \n",
    "            for n,c in graph[p]:\n",
    "                if n in distance:\n",
    "                    prev = distance[n]\n",
    "                else:\n",
    "                    prev = inf\n",
    "                  \n",
    "                now = distance[p] + c\n",
    "                if now < prev:\n",
    "                    distance[n] = now\n",
    "                    if n not in seen:\n",
    "                        Q.append(n)\n",
    "                        seen.add(n)\n",
    "        \n",
    "        return distance[target]\n",
    "                    \n",
    "                \n",
    "    \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        cnt = 0\n",
    "        pId = dict()\n",
    "        g = defaultdict(list)\n",
    "        def add_node(x, y):\n",
    "            nonlocal cnt\n",
    "            if (x,y) in pId:\n",
    "                return pId[(x,y)]\n",
    "            else:\n",
    "                pId[(x,y)] = cnt\n",
    "                cnt += 1\n",
    "                return pId[(x,y)]\n",
    "\n",
    "        def dist(x1,y1, x2,y2):\n",
    "            return abs(x1 -x2) + abs(y1-y2)\n",
    "\n",
    "        def add_edge(x1,y1, x2, y2, d):\n",
    "            u = add_node(x1,y1)\n",
    "            v = add_node(x2,y2)\n",
    "            g[u].append((v, d))\n",
    "        \n",
    "        for i, [x1,y1, x2,y2,w] in enumerate(specialRoads):\n",
    "            d = min(dist(x1,y1,x2,y2), w)\n",
    "            add_edge(x1,y1, x2, y2, d)\n",
    "            add_edge(start[0], start[1], x1,y1, dist(start[0], start[1], x1,y1))\n",
    "            add_edge(x2, y2, target[0],target[1], dist(x2, y2, target[0],target[1]))\n",
    "\n",
    "        for i, [x1,y1, x2,y2,w] in enumerate(specialRoads):\n",
    "            for j, [u1,v1, u2, v2, w1] in enumerate(specialRoads):\n",
    "                if i != j:\n",
    "                    add_edge(x2,y2, u1,v1, dist(x2,y2, u1,v1))\n",
    "                    add_edge(u2,v2, x1,y1, dist(u2,v2, x1,y1)) \n",
    "        \n",
    "        add_edge(start[0], start[1], target[0],target[1], dist(start[0], start[1], target[0], target[1]))\n",
    "\n",
    "        sId = pId[tuple(start)]\n",
    "        eId = pId[tuple(target)]\n",
    "        dist = [float('inf')] * cnt \n",
    "        vis = [0] *cnt \n",
    "        dist[sId] = 0\n",
    "\n",
    "        for _ in range(cnt):\n",
    "            u = -1\n",
    "            for i in range(cnt):\n",
    "                if not vis[i] and (u == -1 or dist[i] < dist[u]):\n",
    "                    u = i \n",
    "            vis[u ] = 1\n",
    "\n",
    "            for v,w in g[u]:\n",
    "                dist[v] = min(dist[v], dist[u] + w)\n",
    "        \n",
    "        return dist[eId]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        ''' 数据比较大，建图不好搞\n",
    "            需要做一个转换，不可能对于每一二维坐标系的点都考虑\n",
    "            事实上，只需要考虑 起点、终点、特殊路径的终点即可\n",
    "        '''\n",
    "\n",
    "        n = len(specialRoads)\n",
    "        nxs = [[] for _ in range(n + 2)]  # 0 start n+1 target\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            s_dis = min(abs(specialRoads[i - 1][2] - start[0]) + abs(specialRoads[i - 1][3] - start[1]),\n",
    "                        abs(specialRoads[i - 1][0] - start[0]) + abs(specialRoads[i - 1][1] - start[1]) + specialRoads[i-1][-1])\n",
    "            nxs[0].append((i, s_dis))\n",
    "            e_dis = abs(specialRoads[i - 1][2] - target[0]) + abs(specialRoads[i - 1][3] - target[1])\n",
    "            nxs[i].append((n+1, e_dis))\n",
    "            for j in range(1, n + 1):\n",
    "                if i != j:\n",
    "                    x1, y1, x2, y2, c1 = specialRoads[i - 1][0], specialRoads[i - 1][1], specialRoads[i - 1][2], specialRoads[i - 1][3],specialRoads[i - 1][-1]\n",
    "                    x3, y3, x4, y4, c2 = specialRoads[j - 1][0], specialRoads[j - 1][1], specialRoads[j - 1][2], specialRoads[j - 1][3],specialRoads[j - 1][-1]\n",
    "                    nxs[i].append((j, min(abs(x4-x2)+abs(y4-y2), abs(x3-x2)+abs(y3-y2) + c2)))\n",
    "                    nxs[j].append((i, min(abs(x4-x2)+abs(y4-y2), abs(x4-x1)+abs(y4-y1) + c1)))\n",
    "\n",
    "        nxs[0].append((n+1, abs(target[0] - start[0]) + abs(target[1] - start[1])))\n",
    "\n",
    "        dis = [inf for _ in range(n+2)]\n",
    "        dis[0] = 0\n",
    "        q = [(0, 0)] # 距离0，当前编号0\n",
    "        while q:\n",
    "            d, node = heapq.heappop(q)\n",
    "            if node == n+1:\n",
    "                return d\n",
    "            if d > dis[node]: continue\n",
    "            for nx, nxdis in nxs[node]:\n",
    "                if d + nxdis < dis[nx]:\n",
    "                    dis[nx] = d + nxdis\n",
    "                    heapq.heappush(q, (d + nxdis, nx))\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        # 每一步的终点必须是target或者specialRoads的起点和终点\n",
    "        ends = {tuple(target)}\n",
    "        road = defaultdict(dict)\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            road[(x1, y1)][(x2, y2)] = min(road[(x1, y1)].get((x2, y2), maxsize), cost)\n",
    "            ends |= {(x1, y1), (x2, y2)}\n",
    "        ends = list(ends)\n",
    "\n",
    "        dist = {}  # start到各点的最短距离\n",
    "        h = [[0, *start]]\n",
    "        while h:\n",
    "            d, i, j = heappop(h)\n",
    "            if [i, j] == target:\n",
    "                return d\n",
    "            if d >= dist.get((i, j), maxsize):\n",
    "                continue\n",
    "            dist[(i, j)] = d\n",
    "\n",
    "            for ii, jj in ends:\n",
    "                temp = min(abs(ii - i) + abs(jj - j), road[(i, j)].get((ii, jj), maxsize))\n",
    "                if d + temp < dist.get((ii, jj), maxsize):\n",
    "                    heappush(h, [d + temp, ii, jj])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        if start == target :\n",
    "            return 0\n",
    "        P=[tuple(start),tuple(target)]\n",
    "        for a,b,c,d,e in specialRoads:\n",
    "            P+=[(a,b),(c,d)] ;\n",
    "        P=list(set(P))\n",
    "        E=defaultdict(dict)\n",
    "        for a,b in combinations_with_replacement(P,2):\n",
    "            E[a][b]=E[b][a]=abs(a[0]-b[0])+abs(a[1]-b[1])\n",
    "        for a,b,c,d,e in specialRoads:\n",
    "            E[(a,b)][(c,d)] = min(E[(a,b)][(c,d)] ,e)\n",
    "        q=[(0,tuple(start))] \n",
    "        dis=defaultdict(lambda:inf)\n",
    "        while q:\n",
    "            d,x=heappop(q) \n",
    "            if x == tuple(target):\n",
    "                return d \n",
    "            if d > dis[x]: \n",
    "                continue \n",
    "            for y,dd in E[x].items():\n",
    "                if dd+d < dis[y]:\n",
    "                    dis[y] = dd+d \n",
    "                    heappush(q,(dis[y],y))\n",
    "                    \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for x1,y1,x2,y2,c in specialRoads:\n",
    "            graph[(x1, y1)].append(((x2,y2), c))\n",
    "            graph[tuple(start)].append(((x1, y1), abs(x1-start[0])+abs(y1-start[1])))\n",
    "            graph[(x2,y2)].append((tuple(target), abs(x2-target[0])+abs(y2-target[1])))\n",
    "        graph[tuple(start)].append((tuple(target), abs(start[0]-target[0])+abs(start[1]-target[1])))\n",
    "        for i in range(len(specialRoads)-1):\n",
    "            for j in range(i+1, len(specialRoads)):\n",
    "                x1, y1 = specialRoads[i][2:4]\n",
    "                x2, y2 = specialRoads[j][:2]\n",
    "                cost = abs(x1-x2)+abs(y1-y2)\n",
    "                graph[(x1, y1)].append(((x2, y2), cost))\n",
    "                x1, y1 = specialRoads[j][2:4]\n",
    "                x2, y2 = specialRoads[i][:2]\n",
    "                cost = abs(x1-x2)+abs(y1-y2)\n",
    "                graph[(x1, y1)].append(((x2, y2), cost))\n",
    "        q = [(0, tuple(start))]\n",
    "        seen = set()\n",
    "        while q:\n",
    "            dist, node = heapq.heappop(q)\n",
    "            if node in seen:\n",
    "                continue\n",
    "            if node == tuple(target):\n",
    "                return dist\n",
    "            seen.add(node)\n",
    "            for neighbor, nx_dist in graph[node]:\n",
    "                heapq.heappush(q, (dist+nx_dist, neighbor))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        if start[0] == target[0] and start[1] == target[1]:\n",
    "            return 0\n",
    "        d = {(start[0],start[1]):0,(target[0],target[1]):1}\n",
    "        f = [(start[0],start[1]),(target[0],target[1])]\n",
    "        for i in specialRoads:\n",
    "            x = (i[0],i[1])\n",
    "            y = (i[2],i[3])\n",
    "            if x not in d:\n",
    "                d[x] = len(d)\n",
    "                f.append(x)\n",
    "            if y not in d:\n",
    "                d[y] = len(d)\n",
    "                f.append(y)\n",
    "        \n",
    "        l = [[2*(10**5)+1 for i in range(len(d))] for j in range(len(d))]\n",
    "        for i in specialRoads:\n",
    "            x = (i[0],i[1])\n",
    "            y = (i[2],i[3])\n",
    "            l[d[x]][d[y]] = min(l[d[x]][d[y]],i[4])\n",
    "            # l[d[y]][d[x]] = min(l[d[y]][d[x]],i[4])\n",
    "        for i in range(len(d)):\n",
    "            for j in range(len(d)):\n",
    "                l[i][j] = min(l[i][j],abs(f[i][0]-f[j][0])+abs(f[i][1]-f[j][1]))\n",
    "        xx = {0:1}\n",
    "        h = [(l[0][i],i) for i in range(1,len(d))]\n",
    "        heapify(h)\n",
    "        ans = [l[0][i] for i in range(len(d))]\n",
    "        print(d)\n",
    "        for i in range(len(d)):\n",
    "            uu = None\n",
    "            # print(h)\n",
    "            while not uu:\n",
    "                t = heappop(h)\n",
    "                if t[1] not in xx:\n",
    "                    xx[t[1]] = 1\n",
    "\n",
    "                    ans[t[1]] = t[0]\n",
    "                    uu = t[1]\n",
    "            # print(uu,ans)\n",
    "            if t[1] == 1:\n",
    "                break\n",
    "            for j in range(len(d)):\n",
    "                if j not in xx:\n",
    "                    ans[j] = min(ans[j],l[uu][j]+ans[uu])\n",
    "                    heappush(h,(ans[j],j))\n",
    "            \n",
    "        \n",
    "        \n",
    "        return ans[1]\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        m , n = target\n",
    "        graph = defaultdict(lambda :defaultdict(lambda :inf))\n",
    "        for x1 , y1 , x2, y2 , cost in specialRoads:\n",
    "            graph[(x1,y1)][(x2,y2)] = min(graph[(x1,y1)][(x2,y2)],cost)\n",
    "            graph[(x1,y1)][(m,n)] = min(graph[(x1,y1)][(m,n)],abs(m-x1) + abs(n-y1))\n",
    "            graph[(x2,y2)][(m,n)] = min(graph[(x2,y2)][(m,n)],abs(m-x2) + abs(n-y2))\n",
    "            graph[(start[0],start[1])][(x2,y2)] = min(graph[(start[0],start[1])][(x2,y2)],abs(start[0]-x2) + abs(start[1]-y2))\n",
    "            graph[(start[0],start[1])][(x1,y1)] = min(graph[(start[0],start[1])][(x1,y1)],abs(start[0]-x1) + abs(start[1]-y1))\n",
    "            for x , y , x3, y3 , cost in specialRoads:\n",
    "                graph[(x2,y2)][(x,y)] = min(graph[(x2,y2)][(x,y)],abs(x-x2) + abs(y-y2))\n",
    "                graph[(x2,y2)][(x3,y3)] = min(graph[(x2,y2)][(x3,y3)],abs(x3-x2) + abs(y3-y2))\n",
    "\n",
    "        \n",
    "        dist = defaultdict(lambda :inf)\n",
    "        dist[(start[0],start[1])] = 0\n",
    "        dist[(m,n)] = abs(m-start[0]) + abs(n-start[1])\n",
    "        queue = deque([start])\n",
    "        while queue:\n",
    "            i , j = queue.popleft()\n",
    "            for k , v in graph[(i,j)].items():\n",
    "                ni , nj = k\n",
    "                if dist[(ni,nj)] > dist[(i,j)] + v:\n",
    "                    dist[(ni,nj)] = dist[(i,j)] + v\n",
    "                    queue.append((ni,nj))\n",
    "        return dist[(m,n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        if start == target: return 0\n",
    "\n",
    "        points_set = set()\n",
    "        points_set.add((start[0], start[1]))\n",
    "        points_set.add((target[0], target[1]))\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            points_set.add((x1, y1))\n",
    "            points_set.add((x2, y2))\n",
    "        points = list(points_set)\n",
    "        n = len(points)\n",
    "        point_index = {v:i for i, v in enumerate(points)}\n",
    "        dist = [[None] * n for _ in range(n)]\n",
    "        for i, (xi, yi) in enumerate(points):\n",
    "            for j, (xj, yj) in enumerate(points):\n",
    "                dist[i][j] = dist[j][i] = abs(xi-xj) + abs(yi-yj)\n",
    "\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            i1 = point_index[(x1, y1)]\n",
    "            i2 = point_index[(x2, y2)]\n",
    "            if dist[i1][i2] > cost:\n",
    "                dist[i1][i2] = cost\n",
    "        \n",
    "        visited = [False] * n\n",
    "        start_index = point_index[tuple(start)]\n",
    "        target_index = point_index[tuple(target)]\n",
    "        todo = [(0, start_index)]\n",
    "        ans = dist[start_index][target_index]\n",
    "        while todo:\n",
    "            #print(len(todo))\n",
    "            d, src = heapq.heappop(todo)\n",
    "            if visited[src]:\n",
    "                continue\n",
    "            else:\n",
    "                visited[src] = True\n",
    "            if src == target_index:\n",
    "                return d\n",
    "            for dst in range(n):\n",
    "                if not visited[dst]:\n",
    "                    dd = d+dist[src][dst]\n",
    "                    heapq.heappush(todo, (dd, dst))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        def dijkstra(graph, source):\n",
    "            distance = {node:float('inf') for node in graph}\n",
    "            distance[source] = 0\n",
    "\n",
    "            queue = [(0,source)]\n",
    "            while queue:\n",
    "                dis, node = heapq.heappop(queue)\n",
    "\n",
    "                if dis > distance[node]:\n",
    "                    continue\n",
    "\n",
    "                for nxt in graph[node]:\n",
    "                    new_dis = dis + graph[node][nxt]\n",
    "                    if new_dis < distance[nxt]:\n",
    "                        distance[nxt] = new_dis\n",
    "                        heapq.heappush(queue, (new_dis, nxt))\n",
    "            return distance\n",
    "\n",
    "        graph = {}\n",
    "        for spe in specialRoads:\n",
    "            x1,y1,x2,y2,cost = spe\n",
    "            s = (x1,y1)\n",
    "            t = (x2,y2)\n",
    "            if s not in graph:\n",
    "                graph[s] = {}\n",
    "            if t not in graph:\n",
    "                graph[t] = {}\n",
    "            if t not in graph[s]:\n",
    "                graph[s][t] = min(cost,abs(t[0]-s[0]) + abs(t[1]-s[1]))\n",
    "            else:\n",
    "                graph[s][t] = min(cost, graph[s][t])\n",
    "\n",
    "            if (start[0],start[1]) not in graph:\n",
    "                graph[(start[0],start[1])] = {}\n",
    "            if (target[0],target[1]) not in graph:\n",
    "                graph[(target[0],target[1])] = {}\n",
    "\n",
    "        for n1 in graph:\n",
    "            for n2 in graph:\n",
    "                dis = abs(n1[0]-n2[0]) + abs(n1[1]-n2[1])\n",
    "                if n2 not in graph[n1] or dis < graph[n1][n2]:\n",
    "                    graph[n1][n2] = dis\n",
    "        distance = dijkstra(graph, (start[0],start[1]))\n",
    "        return distance[(target[0],target[1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "from collections import defaultdict, deque\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]\n",
    "        :param start:\n",
    "        :param target:\n",
    "        :param specialRoads:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "\n",
    "        target = tuple(target)\n",
    "        start = tuple(start)\n",
    "        for i in specialRoads:\n",
    "            ans1 = abs(i[3] - i[1]) + abs(i[2] - i[0])\n",
    "            if i[4] >= ans1:\n",
    "                continue\n",
    "            m1[(i[0], i[1])].append((i[2], i[3], i[4]))\n",
    "\n",
    "        total = abs(target[0] - start[0]) + abs(target[1] - start[1])\n",
    "        def get_dist(a, b):\n",
    "            return abs(a[0] - b[0]) + abs(a[1] - b[1])\n",
    "\n",
    "        dq = deque()\n",
    "        dq.append((start, 0))\n",
    "        usedM = {}\n",
    "        while len(dq) > 0:\n",
    "            idx, cost1 = dq.popleft()\n",
    "\n",
    "            if cost1 + get_dist(idx, target) < total:\n",
    "                total = cost1 + get_dist(idx, target)\n",
    "            if idx not in usedM:\n",
    "                usedM[idx] = cost1\n",
    "            else:\n",
    "                if cost1 >= usedM[idx]:\n",
    "                    continue\n",
    "                usedM[idx] = cost1\n",
    "            for i in m1:\n",
    "\n",
    "                cost11 = get_dist(i, idx)\n",
    "                for j in m1[i]:\n",
    "                    cost2 = j[2]\n",
    "                    newidx = j[0], j[1]\n",
    "                    dq.append((newidx, cost1 + cost11 + cost2))\n",
    "\n",
    "        return total\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def coord2num(x1, y1):\n",
    "    return x1 * 100001 + y1\n",
    "\n",
    "\n",
    "def num2coord(num):\n",
    "    return num // 100001, num % 100001\n",
    "\n",
    "\n",
    "def dist(x1, y1, x2, y2):\n",
    "    return abs(x1 - x2) + abs(y1 - y2)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        vs = set()\n",
    "        vf = coord2num(*start)\n",
    "        ve = coord2num(*target)\n",
    "        vs.add(vf)\n",
    "        vs.add(ve)\n",
    "        adj_tbl = defaultdict(dict)\n",
    "        for special_road in specialRoads:\n",
    "            x1, y1, x2, y2, c = special_road\n",
    "            v1, v2 = coord2num(x1, y1), coord2num(x2, y2)\n",
    "            vs.add(v1)\n",
    "            vs.add(v2)\n",
    "            adj_tbl[v1][v2] = min(c, dist(x1, y1, x2, y2), adj_tbl.get(v1, dict()).get(v2, inf))\n",
    "\n",
    "        vl = list(sorted(vs))\n",
    "        for i in range(len(vl)):\n",
    "            for j in range(len(vl)):\n",
    "                if i == j: continue\n",
    "                v1, v2 = vl[i], vl[j]\n",
    "                x1, y1 = num2coord(v1)\n",
    "                x2, y2 = num2coord(v2)\n",
    "                adj_tbl[v1][v2] = min(adj_tbl.get(v1, dict()).get(v2, inf), dist(x1, y1, x2, y2))\n",
    "\n",
    "        dis = defaultdict(lambda:float(\"inf\"))\n",
    "        dis[vf] = 0\n",
    "        q = [(0, vf)]\n",
    "        vis = set()\n",
    "        while q:\n",
    "            _, u = heapq.heappop(q)\n",
    "            if u in vis: continue\n",
    "            vis.add(u)\n",
    "            for v, w in adj_tbl[u].items():\n",
    "                if dis[v] > dis[u] + w:\n",
    "                    dis[v] = dis[u] + w\n",
    "                    heapq.heappush(q, (dis[v], v))\n",
    "        return dis[ve]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        ans = abs(target[1]-start[1])+abs(target[0]-start[0])\n",
    "        g = {}\n",
    "        begin = start[0]*100000 +start[1]\n",
    "        end = target[0]*100000+target[1]\n",
    "        g[begin] = []\n",
    "        dist = {}\n",
    "        vis = {}\n",
    "        vis[begin]=False\n",
    "        vis[end] = False\n",
    "        \n",
    "        dist[end] = ans\n",
    "        for sr in specialRoads:\n",
    "            x = sr[0]*100000+sr[1]\n",
    "            y = sr[2]*100000+sr[3]\n",
    "            dist[x] = inf\n",
    "            dist[y] = inf\n",
    "            vis[x] = False\n",
    "            vis[y] =False\n",
    "            if x not in g:\n",
    "                g[x] = []\n",
    "            g[x].append([y,sr[4]])\n",
    "            if begin!=x:\n",
    "                g[begin].append([x,abs(start[0]-sr[0])+abs(start[1]-sr[1])]) \n",
    "            if end!=y:\n",
    "                if y not in g:g[y] = []\n",
    "                g[y].append([end,abs(target[0]-sr[2])+abs(target[1]-sr[3])])\n",
    "    \n",
    "        for sr in specialRoads:\n",
    "            for sr2 in specialRoads:\n",
    "                x = sr[0]*100000+sr[1]\n",
    "                y = sr[2]*100000+sr[3]\n",
    "                x2 = sr2[0]*100000+sr2[1]\n",
    "                y2 = sr2[2]*100000+sr2[3]\n",
    "                if y not in g:g[y]=[]\n",
    "                if y2 not in g:g[y2] =[]\n",
    "                if y !=x2:\n",
    "                    g[y].append([x2,abs(sr[2]-sr2[0])+abs(sr[3]-sr2[1])])\n",
    "                if y2!=x:\n",
    "                    g[y2].append([x,abs(sr2[2]-sr[0])+abs(sr2[3]-sr[1])])\n",
    "    \n",
    "        dist[begin]=0\n",
    "        q = []\n",
    "        heappush(q,[0,begin])\n",
    "        while q:\n",
    "            _,x = heappop(q)\n",
    "            if vis[x]:continue\n",
    "            vis[x] = True\n",
    "            if x not in g:continue\n",
    "            for y,c in g[x]:\n",
    "                if dist[y] > dist[x]+c:\n",
    "                    dist[y] = dist[x]+c\n",
    "                    heappush(q,[dist[y],y])\n",
    "\n",
    "        return min(dist[end],ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        def manhattanDist(a, b):\n",
    "            return abs(a[0]-b[0]) + abs(a[1]-b[1])\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        points = [tuple(start), tuple(target)]\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            points.append((x1, y1))\n",
    "            points.append((x2, y2))\n",
    "\n",
    "        points = list(set(points))\n",
    "        points.sort()\n",
    "        for i, p1 in enumerate(points):\n",
    "            for j in range(i+1, len(points)):\n",
    "                p2 = points[j]\n",
    "                cost = manhattanDist(p1, p2)\n",
    "                graph[p1].append((cost, p2))\n",
    "                graph[p2].append((cost, p1))\n",
    "\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            graph[(x1, y1)].append((cost, (x2, y2)))  # only consider one direction\n",
    "\n",
    "        dist = {node: float('inf') for node in graph}\n",
    "        dist[tuple(start)] = 0\n",
    "        heap = [(0, tuple(start))]\n",
    "\n",
    "        while heap:\n",
    "            curr_dist, curr_node = heapq.heappop(heap)\n",
    "            if curr_dist > dist[curr_node]:\n",
    "                continue\n",
    "            for next_dist, next_node in graph[curr_node]:\n",
    "                new_dist = curr_dist + next_dist\n",
    "                if new_dist < dist[next_node]:\n",
    "                    dist[next_node] = new_dist\n",
    "                    heapq.heappush(heap, (new_dist, next_node))\n",
    "\n",
    "        return dist[tuple(target)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        points = set()\n",
    "        points.add(tuple(start))\n",
    "        points.add(tuple(target))\n",
    "        roads = dict()\n",
    "        for (sx, sy, ex, ey, cost) in specialRoads:\n",
    "            if (sx, sy, ex, ey) not in roads or roads[(sx, sy, ex, ey)] > cost:\n",
    "                roads[(sx, sy, ex, ey)] = cost\n",
    "            points.add((sx, sy))\n",
    "            points.add((ex, ey))\n",
    "        points = list(points)\n",
    "        s_idx = points.index(tuple(start))\n",
    "        e_idx = points.index(tuple(target))\n",
    "        N = len(points)\n",
    "        A = [[0] * N for _ in range(N)]\n",
    "        for i in range(N):\n",
    "            for j in range(N):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                p1x, p1y = points[i]\n",
    "                p2x, p2y = points[j]\n",
    "                common = abs(p1x - p2x) + abs(p1y - p2y)\n",
    "                if (p1x, p1y, p2x, p2y) in roads and roads[(p1x, p1y, p2x, p2y)] < common:\n",
    "                    common = roads[(p1x, p1y, p2x, p2y)]\n",
    "                A[i][j] = common\n",
    "        vis = [inf] * N\n",
    "        queue = [(0, s_idx)]\n",
    "        while len(queue) > 0:\n",
    "            distance, i = heapq.heappop(queue)\n",
    "            if vis[i] < inf:\n",
    "                continue\n",
    "            if i == e_idx:\n",
    "                return distance\n",
    "            vis[i] = distance\n",
    "            for j in range(N):\n",
    "                if vis[j] == inf:\n",
    "                    new_distance = distance + A[i][j]\n",
    "                    heapq.heappush(queue, (new_distance, j))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "import sys, time\n",
    "import operator\n",
    "import heapq\n",
    "\n",
    "from typing import *\n",
    "from bisect import *\n",
    "from collections import *\n",
    "from functools import *\n",
    "from itertools import *\n",
    "from math import *\n",
    "\n",
    "\n",
    "class SPA:\n",
    "    def __init__(self):\n",
    "        self.g = defaultdict(defaultdict)\n",
    "    def add_edge(self,p1,p2,d):\n",
    "        if d<self.g[p1].get(p2, math.inf):\n",
    "            self.g[p1][p2]=d\n",
    "    def dijk(self,startp):   # 返回DIS数组\n",
    "        \"\"\"\n",
    "        单点出发最短路startp\n",
    "        \"\"\"\n",
    "        q=[]            # 作为优先队列\n",
    "        vis_pop = set() # 是否曾经弹出过\n",
    "        dis = defaultdict(lambda :math.inf)  # dis[j]存储startp到j结果\n",
    "        dis[startp]=0\n",
    "        heapq.heappush(q,(dis[startp],startp))\n",
    "        while q:\n",
    "            _,point = heapq.heappop(q)\n",
    "            if point in vis_pop:\n",
    "                continue\n",
    "            vis_pop.add(point)\n",
    "            to_update = self._getpointfrom(point)\n",
    "            for to_d,to_p in to_update:\n",
    "                if dis[point]+to_d<dis[to_p]:\n",
    "                    dis[to_p] = dis[point]+to_d\n",
    "                    heapq.heappush(q,(dis[to_p],to_p))\n",
    "        return dis\n",
    "    def _getpointfrom(self,point):\n",
    "        # 如果是完全图,直接取出所有点\n",
    "        return [(self.g[point][p], p) for p in self.g[point]]\n",
    "        \n",
    "        \n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        z=SPA()\n",
    "        points=set()\n",
    "        points|={tuple(start),tuple(target)}\n",
    "        for a, b, c, d, e in specialRoads:\n",
    "            points|={(a,b), (c,d)}\n",
    "            z.add_edge((a,b), (c,d),e)\n",
    "        [z.add_edge(p1,p2,abs(p1[0]-p2[0])+abs(p1[1]-p2[1])) for p1 in points for p2 in points]\n",
    "        return z.dijk(tuple(start))[tuple(target)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        \n",
    "        n = len(specialRoads)\n",
    "        \n",
    "        sx, sy = start\n",
    "        tx, ty = target\n",
    "        \n",
    "        graph = defaultdict(set)\n",
    "        \n",
    "        # 开始位置到特殊路径上位置的距离\n",
    "        for x1, y1, x2, y2, _ in specialRoads:\n",
    "            if (x1, y1) != (sx, sy):\n",
    "                graph[(sx, sy)].add(((x1, y1), abs(x1 - sx) + abs(y1 - sy)))\n",
    "            if (x2, y2) != (sx, sy):\n",
    "                graph[(sx, sy)].add(((x2, y2), abs(x2 - sx) + abs(y2 - sy)))\n",
    "\n",
    "                \n",
    "        # 特殊路径上位置到结束位置的距离\n",
    "        for x1, y1, x2, y2, _ in specialRoads:\n",
    "            if (x1, y1) != (tx, ty):\n",
    "                graph[(x1, y1)].add(((tx, ty), abs(tx - x1) + abs(ty - y1)))\n",
    "            if (x2, y2) != (tx, ty):\n",
    "                graph[(x2, y2)].add(((tx, ty), abs(tx - x2) + abs(ty - y2)))\n",
    "                \n",
    "        # 特殊路径\n",
    "        for x1, y1, x2, y2, c in specialRoads:\n",
    "            graph[(x1, y1)].add(((x2, y2), c))\n",
    "                \n",
    "        # 特殊路径上位置之间的距离\n",
    "        for i in range(n):\n",
    "            x1, y1, _, _, _ = specialRoads[i]\n",
    "            for j in range(n):\n",
    "                _, _, x2, y2, _ = specialRoads[j]\n",
    "                if i != j:\n",
    "                    graph[(x1, y1)].add(((x2, y2), abs(x2 - x1) + abs(y2 - y1)))\n",
    "                    if (x2, y2) != (tx, ty):\n",
    "                        graph[(x2, y2)].add(((x1, y1), abs(x2 - x1) + abs(y2 - y1)))\n",
    "                    \n",
    "                \n",
    "        def dijkstra(e,s):\n",
    "            dis = defaultdict(lambda: inf)\n",
    "            dis[s] = 0\n",
    "            q = [(0, s)]\n",
    "            vis = set()\n",
    "            while q:\n",
    "                _, u = heapq.heappop(q)\n",
    "                if u in vis: continue\n",
    "                vis.add(u)\n",
    "                for v, w in e[u]:\n",
    "                    if dis[v] > dis[u] + w:\n",
    "                        dis[v] = dis[u] + w\n",
    "                        heapq.heappush(q, (dis[v], v))\n",
    "            return dis\n",
    "        \n",
    "        dis = dijkstra(graph, (sx, sy))\n",
    "        \n",
    "        return dis[(tx, ty)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: List[int], t: List[int], sprs: List[List[int]]) -> int:\n",
    "        if s[0] == t[0] and s[1] == t[1]: return 0\n",
    "        inds = {(s[0], s[1]): 0, (t[0], t[1]): 1}\n",
    "        for x1, y1, x2, y2, _ in sprs:\n",
    "            if (x1, y1) not in inds:\n",
    "                inds[(x1, y1)] = len(inds)\n",
    "            if (x2, y2) not in inds:\n",
    "                inds[(x2, y2)] = len(inds)\n",
    "                \n",
    "        n = len(inds)\n",
    "        e = [[] for _ in range(n)]\n",
    "        spr = defaultdict(set)\n",
    "        for x1, y1, x2, y2, c in sprs:\n",
    "            d = abs(x1 - x2) + abs(y1 - y2)\n",
    "            e[inds[(x1, y1)]].append((inds[(x2, y2)], min(d, c)))\n",
    "            spr[inds[(x1, y1)]].add(inds[(x2, y2)])\n",
    "            \n",
    "        for (x1, y1), ind1 in inds.items():\n",
    "            for (x2, y2), ind2 in inds.items():\n",
    "                if ind1 == ind2 or ind2 in spr[ind1]: continue\n",
    "                e[ind1].append((ind2, abs(x1 - x2) + abs(y1 - y2)))\n",
    "        \n",
    "        dist = [-1] * n\n",
    "        dist[0] = 0\n",
    "        que = [(0, 0)]\n",
    "        while que:\n",
    "            d, u = que[0]\n",
    "            heappop(que)\n",
    "            if u == 1: return dist[1]\n",
    "            if dist[u] < d: continue\n",
    "            for v, c in e[u]:\n",
    "                if dist[v] == -1 or dist[v] > d + c:\n",
    "                    dist[v] = d + c\n",
    "                    heappush(que, (dist[v], v))\n",
    "                    \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n = 10 ** 5 + 1\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        nodes = set()\n",
    "        nodes.add(tuple(start))\n",
    "        nodes.add(tuple(target))\n",
    "        d = {}\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            nodes.add((x1, y1))\n",
    "            nodes.add((x2, y2))\n",
    "            if (x1, y1, x2, y2) in d:\n",
    "                d[(x1, y1, x2, y2)] = min(d[(x1, y1, x2, y2)], cost) # 考虑输入的specialRoads也有重边, 这一步是必要的\n",
    "            else:\n",
    "                d[(x1, y1, x2, y2)] = cost\n",
    "        g = defaultdict(list) # {(x1, y1): [(x2, y2, cost), (x3, y3, cost)...]}\n",
    "        # 建完全图, 图中只有起点, 终点和特殊路径的起点和终点, 因为是曼哈顿距离, 并不需要考虑矩阵的每一个点\n",
    "        for x1, y1 in nodes:\n",
    "            for x2, y2 in nodes:\n",
    "                if x1 == x2 and y1 == y2: continue\n",
    "                g[(x1, y1)].append((x2, y2, min(abs(x1-x2)+abs(y1-y2), d.get((x1, y1, x2, y2), inf))))\n",
    "        # 建图我们只需考虑直连的边, 如果有重边取最小即可, 至于求最短路跑dijkstra即可\n",
    "        # print(g)\n",
    "        \n",
    "        dis = {} # {(x, y): 从start到(x,y)的最短距离}, 需要初始化为inf\n",
    "        dis[(start[0], start[1])] = 0\n",
    "        pq = [(0, start[0], start[1])]\n",
    "        while pq:\n",
    "            d, x, y = heappop(pq)\n",
    "            if x == target[0] and y == target[1]: return d\n",
    "            if d > dis.get((x, y), inf): continue\n",
    "            for nx, ny, w in g[(x, y)]:\n",
    "                if d + w < dis.get((nx, ny), inf):\n",
    "                    dis[(nx, ny)] = d + w\n",
    "                    heappush(pq, (dis[(nx, ny)], nx, ny))\n",
    "        # return dis[(target[0], target[1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        def getDistance(x1, y1, x2, y2):\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "        # 二叉堆优化 Dijkstra 算法\n",
    "        distance = [(0, tuple(start))]\n",
    "        visited = set()\n",
    "        while True:\n",
    "            # 找到距离起点最近的点集邻居顶点\n",
    "            d, (x, y) = heapq.heappop(distance)\n",
    "            while (x, y) in visited:\n",
    "                d, (x, y) = heapq.heappop(distance)\n",
    "            if (x, y) == tuple(target):\n",
    "                return d\n",
    "            # 将该点加入点集，并更新点集邻居与起点的距离\n",
    "            visited.add((x, y))\n",
    "            for x1, y1, x2, y2, cost in specialRoads:\n",
    "                # 使用特殊路径到达出口\n",
    "                if (x, y) == (x1, y1):\n",
    "                    heapq.heappush(distance, (d + cost, (x2, y2)))\n",
    "                # 到所有特殊路径的入口\n",
    "                else:\n",
    "                    heapq.heappush(distance, (d + getDistance(x, y, x1, y1), (x1, y1)))\n",
    "                # 直接到达终点\n",
    "                heapq.heappush(distance, (d + getDistance(x, y, *target), tuple(target)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        ps = set()\n",
    "        for x1, y1, x2, y2, c in specialRoads:\n",
    "            ps.add((x1, y1))\n",
    "            ps.add((x2, y2))\n",
    "        start, target = tuple(start), tuple(target)\n",
    "        ps.add(start)\n",
    "        ps.add(target)\n",
    "        ps = list(ps)\n",
    "        p2i = dict((ps[i], i) for i in range(len(ps)))\n",
    "        cost = dict()\n",
    "        for x1, y1, x2, y2, c in specialRoads:\n",
    "            idx = (p2i[(x1, y1)], p2i[(x2, y2)])\n",
    "            cost[idx] = min(cost.get(idx, float('inf')), c, abs(x2-x1)+abs(y2-y1))\n",
    "        adj = defaultdict(list)\n",
    "        for i in range(len(ps)):\n",
    "            if i == p2i[target]: continue\n",
    "            for j in range(len(ps)):\n",
    "                if j == p2i[start] or j == i: continue\n",
    "                d = abs(ps[j][0]-ps[i][0])+abs(ps[j][1]-ps[i][1])\n",
    "                if cost.get((i, j), None) is not None:\n",
    "                    d = min(d, cost[(i, j)])\n",
    "                adj[i].append((j, d))\n",
    "\n",
    "        h, dis = [], {p2i[start]: 0}\n",
    "        heappush(h, (dis[p2i[start]], p2i[start]))\n",
    "        while h:\n",
    "            d, i = heappop(h)\n",
    "            if d > dis[i]: continue\n",
    "            for j, t in adj[i]:\n",
    "                if dis.get(j, float('inf')) > d+t:\n",
    "                    dis[j] = d+t\n",
    "                    heappush(h, (dis[j], j))\n",
    "        return dis[p2i[target]]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        \n",
    "        nodes = {tuple(start), tuple(target)}\n",
    "        for a, b, c, d, w in specialRoads:\n",
    "            nodes.add((a, b))\n",
    "            nodes.add((c, d))\n",
    "        nodes = list(nodes)\n",
    "        ind = {node: i for i, node in enumerate(nodes)}\n",
    "        n = len(nodes)\n",
    "        \n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            x1, y1 = nodes[i]\n",
    "            for j in range(i+1, n):\n",
    "                x2, y2 = nodes[j]\n",
    "                w = abs(x2-x1) + abs(y2-y1)\n",
    "                dct[i].append([j, w])\n",
    "                dct[j].append([i, w])\n",
    "                \n",
    "        for a, b, c, d, w in specialRoads:\n",
    "            i, j = ind[(a, b)], ind[(c, d)]\n",
    "            dct[i].append([j, w])\n",
    "            \n",
    "        dis = [inf]*n\n",
    "        stack = [[0, ind[tuple(start)]]]\n",
    "        dis[ind[tuple(start)]] = 0\n",
    "\n",
    "        while stack:\n",
    "            d, i = heapq.heappop(stack)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j, w in dct[i]:\n",
    "                dj = w + d\n",
    "                if dj < dis[j]:\n",
    "                    dis[j] = dj\n",
    "                    heapq.heappush(stack, [dj, j])\n",
    "        \n",
    "        return dis[ind[tuple(target)]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dijkstra(g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "    dist = [inf] * len(g)\n",
    "    dist[start] = 0\n",
    "    h = [(0, start)]\n",
    "    while h:\n",
    "        d, x = heappop(h)\n",
    "        if d > dist[x]:\n",
    "            continue\n",
    "        for y, wt in g[x]:\n",
    "            new_d = dist[x] + wt\n",
    "            if new_d < dist[y]:\n",
    "                dist[y] = new_d\n",
    "                heappush(h, (new_d, y))\n",
    "    return dist\n",
    "class Solution:\n",
    "    def minimumCost(self, s: List[int], t: List[int], sp: List[List[int]]) -> int:\n",
    "        arr={tuple(s),tuple(t)}\n",
    "        for a,b,c,d,cost in sp:\n",
    "            arr|={(a,b),(c,d)}\n",
    "        arr=list(arr)\n",
    "        d={a:i for i,a in enumerate(arr)}\n",
    "        n=len(arr)\n",
    "        g=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j:\n",
    "                    a,b=arr[i]\n",
    "                    c,e=arr[j]\n",
    "                    g[d[(a,b)]].append([d[(c,e)],abs(a-c)+abs(b-e)])\n",
    "        for a,b,c,e,cost in sp:\n",
    "            if cost<abs(a-c)+abs(b-e):\n",
    "                g[d[(a,b)]].append([d[(c,e)],cost])\n",
    "        dij=dijkstra(g,d[tuple(s)])\n",
    "        return dij[d[tuple(t)]]\n",
    "                    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], sp: List[List[int]]) -> int:\n",
    "        name = dict()\n",
    "        index = 1\n",
    "        start_name = str(start[0]) + \"|\" + str(start[1])\n",
    "        name[start_name] = [index, start[0], start[1]]\n",
    "        index += 1\n",
    "        for i, s in enumerate(sp):\n",
    "            x, y, u, v, w = s\n",
    "            t = str(x) + \"|\" + str(y)\n",
    "            if t not in name:\n",
    "                name[t] = [index, x ,y]\n",
    "                index += 1\n",
    "            t =  str(u) + \"|\" + str(v)\n",
    "            if t not in name:\n",
    "                name[t] = [index, u, v]\n",
    "                index += 1\n",
    "        end_name = str(target[0]) + \"|\" + str(target[1])\n",
    "        if end_name not in name:\n",
    "            name[end_name] = [index, target[0], target[1]]\n",
    "            index += 1\n",
    "        \n",
    "        n = len(sp)\n",
    "        h = defaultdict(list)\n",
    "        for a in name.keys():\n",
    "            for b in name.keys():\n",
    "                if a != b:   \n",
    "                    h[name[a][0]].append([name[b][0], abs(name[a][1] - name[b][1]) + abs(name[a][2] - name[b][2])])\n",
    "        for i, s in enumerate(sp):\n",
    "            x, y, u, v, w = s\n",
    "            t1 = str(x) + \"|\" + str(y) \n",
    "            t2 =  str(u) + \"|\" + str(v)\n",
    "            h[name[t1][0]].append([name[t2][0], w])\n",
    "        n = len(h)\n",
    "        st = [0] * (n + 1)\n",
    "        dist = [10**10] * (n + 1)\n",
    "        n = len(h)\n",
    "        dist[1] = 0\n",
    "        for i in range(n):\n",
    "            t = -1\n",
    "            for j in range(1, n + 1):\n",
    "                if st[j] == 0 and (t == -1 or dist[j] < dist[t]):\n",
    "                    t = j\n",
    "            st[t] = 1\n",
    "            for b in h[t]:\n",
    "                if not st[b[0]] and dist[b[0]] > dist[t] + b[1]:\n",
    "                    dist[b[0]] = dist[t] + b[1]\n",
    "\n",
    "        return dist[name[end_name][0]]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        g = defaultdict(lambda : defaultdict(lambda : float(\"inf\")))\n",
    "        nodes = set([tuple(start), tuple(target)])\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            g[(x1, y1)][(x2, y2)] = min(cost, g[(x1, y1)][(x2, y2)])\n",
    "            nodes.add((x1, y1)) \n",
    "            nodes.add((x2, y2)) \n",
    "        \n",
    "        \n",
    "        def default(u, v):\n",
    "            x1, y1 = u\n",
    "            x2, y2 = v\n",
    "            return abs(x1-x2) + abs(y1-y2)\n",
    "        \n",
    "        def shortestPath():\n",
    "            q = [(0, tuple(start))]\n",
    "            dist = {}\n",
    "            while len(q):\n",
    "                d, u = heappop(q)\n",
    "                if u in dist:\n",
    "                    continue\n",
    "                \n",
    "                dist[u] = d\n",
    "                if u == target:\n",
    "                    return d\n",
    "                for v in nodes:\n",
    "                    default_cost = default(u, v)\n",
    "                    cost = min(g[u][v], default_cost)\n",
    "                    if v in dist:\n",
    "                        continue\n",
    "                    heappush(q, (d + cost, v))\n",
    "            return dist[(tuple(target))]\n",
    "        return shortestPath()\n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        g = defaultdict(dict)\n",
    "        def get(x,y):\n",
    "            return x * 1000000+y \n",
    "        def add_edge(u,v,w):\n",
    "            if v in g[u]:\n",
    "                g[u][v] = min(g[u][v],w)\n",
    "            else:\n",
    "                g[u][v] = w \n",
    "        def manhadun(x1,y1,x2,y2):\n",
    "            return abs(x1-x2) + abs(y1-y2)\n",
    "        sx,sy = start\n",
    "        tx,ty = target\n",
    "        s,t = get(sx,sy),get(tx,ty)\n",
    "        add_edge(s,t,manhadun(tx,ty,sx,sy))\n",
    "        ps = {(sx,sy),(tx,ty)}\n",
    "        def add_p(x,y):\n",
    "            ps.add((x,y))\n",
    "        for x1,y1,x2,y2,w in specialRoads:\n",
    "            add_p(x1,y1)\n",
    "            add_p(x2,y2)\n",
    "\n",
    "            u,v = get(x1,y1),get(x2,y2)\n",
    "            add_edge(u,v,w)\n",
    "            add_edge(s,u,manhadun(sx,sy,x1,y1))\n",
    "            add_edge(v,t,manhadun(x2,y2,tx,ty))\n",
    "        \n",
    "        for x1,y1 in ps:\n",
    "            u = get(x1,y1)\n",
    "            for x2,y2 in ps:\n",
    "                v = get(x2,y2)\n",
    "                add_edge(u,v,manhadun(x2,y2,x1,y1))\n",
    "        \n",
    "        dis = defaultdict(lambda : inf)\n",
    "        q = [(0,s)]\n",
    "        while q:\n",
    "            c,u = heappop(q)\n",
    "            if u == t :\n",
    "                return c\n",
    "            if c > dis[u]:continue \n",
    "            for v, w in g[u].items():\n",
    "                d = c + w \n",
    "                if d < dis[v]:\n",
    "                    dis[v] = d \n",
    "                    heappush(q,(d,v))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumCost(self, start: List[int], target: List[int], sr: List[List[int]]) -> int:\n",
    "        n = len(sr)\n",
    "        nn = n * 2 + 2\n",
    "        g = [[] for _ in range(nn)]  # n*2:start, n*2+1:target\n",
    "\n",
    "        def add_edge(i, j, c):\n",
    "            g[i].append([j, c])\n",
    "            g[j].append([i, c])\n",
    "\n",
    "        add_edge(n * 2, n * 2 + 1, abs(start[0] - target[0]) + abs(start[1] - target[1]))\n",
    "        for i, (x1, y1, x2, y2, cost) in enumerate(sr):\n",
    "            add_edge(n * 2, i * 2, abs(x1 - start[0]) + abs(y1 - start[1]))\n",
    "            add_edge(n * 2, i * 2 + 1, abs(x2 - start[0]) + abs(y2 - start[1]))\n",
    "            add_edge(n * 2 + 1, i * 2, abs(x1 - target[0]) + abs(y1 - target[1]))\n",
    "            add_edge(n * 2 + 1, i * 2 + 1, abs(x2 - target[0]) + abs(y2 - target[1]))\n",
    "            g[i * 2].append([i * 2 + 1, cost])\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                add_edge(i * 2, j * 2, abs(sr[i][0] - sr[j][0]) + abs(sr[i][1] - sr[j][1]))\n",
    "                add_edge(i * 2, j * 2 + 1, abs(sr[i][0] - sr[j][2]) + abs(sr[i][1] - sr[j][3]))\n",
    "                add_edge(i * 2 + 1, j * 2, abs(sr[i][2] - sr[j][0]) + abs(sr[i][3] - sr[j][1]))\n",
    "                add_edge(i * 2 + 1, j * 2 + 1, abs(sr[i][2] - sr[j][2]) + abs(sr[i][3] - sr[j][3]))\n",
    "\n",
    "        INF = int(1e18)\n",
    "\n",
    "        def dijkstra(src: int, next_v: List[List[List[int]]]):\n",
    "            dist, vis = [INF] * (nn), [False] * (nn)\n",
    "            dist[src] = 0\n",
    "            q = [[0, src]]  # cost-v_idx\n",
    "            while q:\n",
    "                mn, idx = heappop(q)\n",
    "                if vis[idx]: continue\n",
    "                for nx_i, nx_c in next_v[idx]:\n",
    "                    if nx_c + mn < dist[nx_i]:\n",
    "                        dist[nx_i] = nx_c + mn\n",
    "                        heappush(q, [dist[nx_i], nx_i])\n",
    "                vis[idx] = True\n",
    "            return dist\n",
    "\n",
    "        dis = dijkstra(n * 2, g)\n",
    "        return dis[n * 2 + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        graph = defaultdict(set)\n",
    "        graph_sub = defaultdict(set)\n",
    "        node_set = set()\n",
    "        for road in specialRoads:\n",
    "            start_x, start_y, end_x, end_y, cost = road             \n",
    "            if abs(start_x - end_x) + abs(start_y - end_y) < cost:\n",
    "                continue\n",
    "            # ss = graph[(start_x, start_y)]\n",
    "            # ss.add((end_x, end_y, cost))\n",
    "            # graph[(start_x, start_y)] = ss\n",
    "            graph[(start_x, start_y)].add((end_x, end_y, cost))\n",
    "\n",
    "            # ss_sub = graph_sub[(start_x, start_y)]\n",
    "            # ss_sub.add((end_x, end_y))\n",
    "            # graph_sub[(start_x, start_y)] = ss_sub\n",
    "            graph_sub[(start_x, start_y)].add((end_x, end_y))\n",
    "\n",
    "            node_set.add((start_x, start_y))\n",
    "            node_set.add((end_x, end_y))\n",
    "\n",
    "        # print(graph)\n",
    "\n",
    "        node_set.add((start[0], start[1]))\n",
    "        node_set.add((target[0], target[1]))\n",
    "        for x1, y1 in node_set:\n",
    "            for x2, y2 in node_set:\n",
    "                if x1 == x2 and y1 == y2:\n",
    "                    continue\n",
    "                if (x2, y2) in graph_sub[x1, y1]:\n",
    "                    continue\n",
    "                d = abs(x1 - x2) + abs(y1 - y2)\n",
    "                graph[(x1, y1)].add((x2, y2, d))                 \n",
    "        \n",
    "        dist = dict()\n",
    "        dist[(start[0], start[1])] = 0\n",
    "        h = [(0, start[0], start[1])]            \n",
    "        heapq.heapify(h)        \n",
    "        visited = set()\n",
    "        while h:\n",
    "            # print(h)\n",
    "            d, x, y = heapq.heappop(h)\n",
    "            visited.add((x, y))\n",
    "            if dist.get((x,y), -1) != d:\n",
    "                continue\n",
    "            for x2, y2, cost in graph[(x, y)]:\n",
    "                if (x2, y2) in visited:\n",
    "                    continue\n",
    "                if cost + d < dist.get((x2, y2), inf):\n",
    "                    dist[(x2, y2)] = cost + d \n",
    "                    heapq.heappush(h, (cost+d, x2, y2))\n",
    "        # print(dist)\n",
    "        return dist[(target[0], target[1])]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        # 变种的dijkstra问题\n",
    "        # 首先进行建图,把所有涉及过的点直接建图，然后在这些点上进行dijkstra\n",
    "        # 两个点之间的距离是原始距离和cost之间的最小值\n",
    "        mx = inf\n",
    "        def dijkstra(be, ed):\n",
    "            # print(be, ed)\n",
    "            dis[be] = 0\n",
    "            h = []\n",
    "            heappush(h, (0, be))\n",
    "            while h:\n",
    "                d, x = heappop(h)\n",
    "                if vis[x]:\n",
    "                    continue\n",
    "                vis[x] = True\n",
    "                for t, y in g[x]:\n",
    "                    dis[y] = min(dis[y], t + d)\n",
    "                    # print(dis[y], t+d)\n",
    "                    heappush(h, (dis[y], y))\n",
    "                # print(dis)\n",
    "            # print(dis)\n",
    "            return dis[ed]\n",
    "                    \n",
    "                \n",
    "        def work(a, b):\n",
    "            return abs(a[0]-b[0]) + abs(a[1]-b[1])\n",
    "        st = set([tuple(start), tuple(target)])\n",
    "        for a, b, c, d, w in specialRoads:\n",
    "            st.add((a, b))\n",
    "            st.add((c, d))\n",
    "        st = list(st)\n",
    "        # print(st)\n",
    "        dic = {}\n",
    "        for i, p in enumerate(st):\n",
    "            dic[p] = i\n",
    "        # print(dic)\n",
    "        n = len(st)\n",
    "        g = [[] for _ in range(n)] #最多500个点\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                g[i].append((work(st[i], st[j]), j))\n",
    "        # print(g)\n",
    "        for a, b, c, d, w in specialRoads:\n",
    "            g[dic[(a,b)]].append((w, dic[c, d]))\n",
    "        # print(g)\n",
    "        # dijkstra,堆优化的\n",
    "        vis = [False] * n\n",
    "        dis = [mx] * n\n",
    "        return dijkstra(dic[tuple(start)], dic[tuple(target)])\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        \n",
    "        knodes = set()\n",
    "        knodes.add(tuple(start))\n",
    "        knodes.add(tuple(target))\n",
    "        \n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            knodes.add((x1, y1))\n",
    "            knodes.add((x2, y2))\n",
    "            \n",
    "        egs = defaultdict(dict)\n",
    "        for x1, y1 in knodes:\n",
    "            for x2, y2 in knodes:\n",
    "                if (x1, y1) != (x2, y2):\n",
    "                    egs[(x1, y1)][(x2, y2)] = abs(x1-x2) + abs(y1-y2)\n",
    "        \n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            if (x1, y1) != (x2, y2) and cost < egs[(x1, y1)][(x2, y2)]:\n",
    "                egs[(x1, y1)][(x2, y2)] = cost\n",
    "                \n",
    "        que = PriorityQueue()\n",
    "        vis = {}\n",
    "        \n",
    "        que.put((0, tuple(start)))\n",
    "        vis[tuple(start)] = 0\n",
    "        while not que.empty():\n",
    "            precost, pre = que.get()\n",
    "            for nxt, v in egs[pre].items():\n",
    "                if vis.get(nxt, 10 ** 10) <= v+precost:\n",
    "                    continue\n",
    "                que.put((v+precost, nxt))\n",
    "                vis[nxt] = v+precost\n",
    "        \n",
    "        return vis[tuple(target)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        roads = defaultdict(dict)\n",
    "        sets = set()\n",
    "        start = tuple(start)\n",
    "        target = tuple(target)\n",
    "        for s in specialRoads:\n",
    "            a,b,c,d,cost = s\n",
    "            sets.add((a,b))\n",
    "            sets.add((c,d))\n",
    "        for s1 in sets:\n",
    "            for s2 in sets:\n",
    "                if s1 == s2:continue\n",
    "                a,b = s1\n",
    "                c,d = s2\n",
    "                roads[(a,b)][(c,d)] = abs(a-c)+abs(b-d)\n",
    "                roads[(c,d)][(a,b)] = abs(a-c)+abs(b-d)\n",
    "        for s1 in sets:\n",
    "            c,d = s1\n",
    "            a,b = start\n",
    "            roads[(a,b)][(c,d)] = abs(a-c)+abs(b-d)\n",
    "            roads[(c,d)][(a,b)] = abs(a-c)+abs(b-d)\n",
    "            a,b = target\n",
    "            roads[(a,b)][(c,d)] = abs(a-c)+abs(b-d)\n",
    "            roads[(c,d)][(a,b)] = abs(a-c)+abs(b-d)\n",
    "        a,b = start\n",
    "        c,d = target\n",
    "        roads[(a,b)][(c,d)] = abs(a-c)+abs(b-d)\n",
    "        roads[(c,d)][(a,b)] = abs(a-c)+abs(b-d)\n",
    "        for s in specialRoads:\n",
    "            a,b,c,d,cost = s\n",
    "            roads[(a,b)][(c,d)] = min([roads[(a,b)][(c,d)] if (c,d) in roads[(a,b)] else math.inf, cost, abs(a-c)+abs(b-d)])\n",
    "            # if (a,b,c,d) == (1,1,1,3): print(roads[(a,b)][(c,d)])\n",
    "            # roads[(c,d)][(a,b)] = min(cost, abs(a-c)+abs(b-d))\n",
    "        heap = [(0,*start)]\n",
    "        dis = dict()\n",
    "        while heap:\n",
    "            deal = heapq.heappop(heap)\n",
    "            dist, a,b = deal\n",
    "            for nex in roads[(a,b)]:\n",
    "                if nex in dis and dis[nex] <= dist+roads[(a,b)][nex]: continue\n",
    "                dis[nex] = dist+roads[(a,b)][nex]\n",
    "                heapq.heappush(heap, (dist+roads[(a,b)][nex], *nex))\n",
    "        # print(sets)\n",
    "        # print(roads)\n",
    "        # print(dis)\n",
    "        return dis[target]\n",
    "            \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        s, t = start, target\n",
    "        pointSet = {(s[0], s[1]), (t[0], t[1])}\n",
    "        tot = defaultdict(dict)\n",
    "        for x1,y1,x2,y2,d in specialRoads:\n",
    "            tot[(x1, y1)][(x2, y2)] = min(tot[(x1, y1)].get((x2, y2), inf), d, abs(x1-x2) + abs(y1-y2))\n",
    "            pointSet.add((x1, y1))\n",
    "            pointSet.add((x2, y2))            \n",
    "        for (x1,y1) in pointSet:\n",
    "            for (x2,y2) in pointSet:\n",
    "                if (x1, y1) != (x2, y2):\n",
    "                    tot[(x1, y1)][(x2, y2)] = min(tot[(x1, y1)].get((x2, y2), inf), abs(x1-x2) + abs(y1-y2))\n",
    "                    tot[(x2, y2)][(x1, y1)] = min(tot[(x2, y2)].get((x1, y1), inf), abs(x1-x2) + abs(y1-y2)) \n",
    "        while True:\n",
    "            dis = tot[(s[0], s[1])]\n",
    "            k = min(dis, key=dis.get)\n",
    "            print(dis, k)\n",
    "            if k == (t[0], t[1]):\n",
    "                return dis[k]\n",
    "            d = dis[k]\n",
    "            del dis[k]\n",
    "            for (x,y), l in dis.items():\n",
    "                dis[(x,y)] = min(dis[(x,y)], d + tot[k].get((x, y)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        def cal_dist(a, b, c ,d):\n",
    "            return abs(a - c) + abs(b - d)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        w = defaultdict(int)\n",
    "        \n",
    "        points = [tuple(start), tuple(target)]\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            points.extend([(x1, y1), (x2, y2)])\n",
    "            if w[((x1, y1), (x2, y2))] == 0 or cost < w[((x1, y1), (x2, y2))]:\n",
    "                w[((x1, y1), (x2, y2))] = cost\n",
    "\n",
    "        n = len(points)\n",
    "        for o in points:\n",
    "            for p in points:\n",
    "                g[o].append(p)\n",
    "                g[p].append(o)\n",
    "\n",
    "                d = cal_dist(*o, *p)\n",
    "                # 有些 特殊路径 比曼哈顿距离还远，所以还是要选择曼哈顿距离\n",
    "                if w[(o, p)] == 0 or d < w[(o, p)]:\n",
    "                    w[(o, p)] = d\n",
    "                if w[(p, o)] == 0 or d < w[(p, o)]:\n",
    "                    w[(p, o)] = d\n",
    "        return self.dijkstra(g, w, tuple(start), tuple(target))\n",
    "\n",
    "\n",
    "    def dijkstra(self, g, w, start, end) -> int:\n",
    "        \"\"\"\n",
    "        g = {a: [b, c, d, ...], b: [e, f, ...], ...}\n",
    "        w = {(a, b): 1, (a, c): 2, ...}\n",
    "        start = a\n",
    "        end = z\n",
    "        \"\"\"\n",
    "        \n",
    "        # 从start到o的最短距离\n",
    "        dist = {o: inf for o in g}\n",
    "        dist[start] = 0\n",
    "        pq = [(0, start)]\n",
    "        heapq.heapify(pq)\n",
    "\n",
    "        while pq:\n",
    "            d, o = heapq.heappop(pq)\n",
    "            if o == end:\n",
    "                return d\n",
    "            if d > dist[o]:\n",
    "                continue\n",
    "            for p in g[o]:\n",
    "                # 从start到p的距离\n",
    "                dist_p = dist[o] + w[(o, p)]\n",
    "                if dist[p] > dist_p:\n",
    "                    dist[p] = dist_p\n",
    "                    heapq.heappush(pq, (dist_p, p))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        def cal_dist(a, b, c ,d):\n",
    "            return abs(a - c) + abs(b - d)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        w = defaultdict(int)\n",
    "        \n",
    "        points = [tuple(start), tuple(target)]\n",
    "        for x1, y1, x2, y2, cost in specialRoads:\n",
    "            points.extend([(x1, y1), (x2, y2)])\n",
    "            if w[((x1, y1), (x2, y2))] == 0 or cost < w[((x1, y1), (x2, y2))]:\n",
    "                w[((x1, y1), (x2, y2))] = cost\n",
    "\n",
    "        n = len(points)\n",
    "        for o in points:\n",
    "            for p in points:\n",
    "                g[o].append(p)\n",
    "                g[p].append(o)\n",
    "\n",
    "                d = cal_dist(*o, *p)\n",
    "                # 有些 特殊路径 比曼哈顿距离还远，所以还是要选择曼哈顿距离\n",
    "                if w[(o, p)] == 0 or d < w[(o, p)]:\n",
    "                    w[(o, p)] = d\n",
    "                if w[(p, o)] == 0 or d < w[(p, o)]:\n",
    "                    w[(p, o)] = d\n",
    "        return self.dijkstra(g, w, tuple(start), tuple(target))\n",
    "\n",
    "\n",
    "    def dijkstra(self, \n",
    "                 g: Dict[int, List[int]], \n",
    "                 w: Dict[Tuple[int, int], int], \n",
    "                 start: int, \n",
    "                 end: int) -> int:\n",
    "        dist = {o: inf for o in g}\n",
    "        dist[start] = 0\n",
    "        pq = [(0, start)]\n",
    "        heapq.heapify(pq)\n",
    "\n",
    "        while pq:\n",
    "            d, o = heapq.heappop(pq)\n",
    "            # 弹出的是d最小的元素，所以当o == end时，d就一定是达到end的最短路径和\n",
    "            ## d从start开始计算，后面弹出的都是比d大的元素，不可能先把小的弹出来\n",
    "            if o == end:\n",
    "                return d\n",
    "            if d > dist[o]:\n",
    "                continue\n",
    "            for p in g[o]:\n",
    "                next_dist = dist[o] + w[(o, p)]\n",
    "                if dist[p] > next_dist:\n",
    "                    dist[p] = next_dist\n",
    "                    heapq.heappush(pq, (next_dist, p))\n",
    "        return float('inf')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        def getDis(a, b):\n",
    "            return abs(a[0] - b[0]) + abs(a[1] - b[1])\n",
    "\n",
    "        def get(nums):\n",
    "            # print(nums)\n",
    "            return nums[0] * 100001 + nums[1]\n",
    "\n",
    "        roads = []\n",
    "        vex = []\n",
    "        vex.append(start)\n",
    "        vex.append(target)\n",
    "        G = defaultdict(list)\n",
    "        for road in specialRoads:\n",
    "            if road[-1] < getDis(road[0:2], road[2:4]):\n",
    "                G[get(road[0:2])].append([get(road[2:4]), road[-1]])\n",
    "                vex.append(road[0:2])\n",
    "                vex.append(road[2:4])\n",
    "\n",
    "        for i in range(len(vex)):\n",
    "            for j in range(len(vex)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                G[get(vex[i])].append([get(vex[j]), getDis(vex[i], vex[j])])\n",
    "                        \n",
    "\n",
    "        dis = {get(v): float('inf') for v in vex}\n",
    "        dis[get(start)] = 0\n",
    "        que = []\n",
    "        que.append([0, get(start)])\n",
    "        while que:\n",
    "            cost,u=heapq.heappop(que)\n",
    "            for v,w in G[u]:\n",
    "                if dis[v]>cost+w:\n",
    "                    dis[v]=cost+w\n",
    "                    heapq.heappush(que,[dis[v],v])\n",
    "        return dis[get(target)]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        all_nodes = [(start[0], start[1]), (target[0], target[1])]\n",
    "        for road in specialRoads:\n",
    "            x1, y1, x2, y2, cost = road\n",
    "            all_nodes.append((x1, y1))\n",
    "            all_nodes.append((x2, y2))\n",
    "            \n",
    "        distance_map = {}\n",
    "        for node1 in all_nodes:\n",
    "            for node2 in all_nodes:\n",
    "                x1, y1 = node1\n",
    "                x2, y2 = node2\n",
    "                distance_map[(node1, node2)] = abs(x1-x2) + abs(y1-y2)\n",
    "        for road in specialRoads:\n",
    "            x1, y1, x2, y2, cost = road\n",
    "            before_cost = abs(x1-x2) + abs(y1-y2)\n",
    "            distance_map[((x1, y1),(x2, y2))] = min(distance_map[((x1, y1),(x2, y2))], cost)\n",
    "        # print(distance_map)\n",
    "        start_node = (start[0], start[1])\n",
    "        target_node = (target[0], target[1])\n",
    "        queue = [(0, start_node)]\n",
    "        visited = {start_node: 0}\n",
    "        heapq.heapify(queue)\n",
    "        while queue:\n",
    "            dis, node = heappop(queue)\n",
    "            # print(dis, node)\n",
    "            if node == target_node:\n",
    "                return dis\n",
    "            for next_node in all_nodes:\n",
    "                cost = distance_map[(node, next_node)]\n",
    "                if next_node not in visited or dis + cost < visited[next_node]:                        \n",
    "                    # queue.append((dis+cost, next_node))\n",
    "                    heappush(queue, (dis+cost, next_node))\n",
    "                    visited[next_node]  = dis+cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        def distance(pos1, pos2):\n",
    "            return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])\n",
    "        nodes = [tuple(start), tuple(target)] + [tuple(road[:2]) for road in specialRoads] + [tuple(road[2:4]) for road in specialRoads]\n",
    "        print(nodes)\n",
    "        cache = {}\n",
    "        for road in specialRoads:\n",
    "            if (road[0],road[1]) not in cache:\n",
    "                cache[(road[0],road[1])] = []\n",
    "            cache[(road[0],road[1])].append((road[2],road[3],road[4]))\n",
    "        graph = {}\n",
    "        for i in range(len(nodes)):\n",
    "            graph[i] = []\n",
    "            for j in range(len(nodes)):\n",
    "                if i != j:\n",
    "                    cost = distance(nodes[i], nodes[j])\n",
    "                    if nodes[i] in cache:\n",
    "                        for tmp in cache[nodes[i]]:\n",
    "                            if tmp[0] == nodes[j][0] and tmp[1] == nodes[j][1]:\n",
    "                                cost = min(cost, tmp[2])\n",
    "                    graph[i].append((j, cost))\n",
    "\n",
    "        # Dijkstra's algorithm\n",
    "        queue = [(0, 0)]  # (cost, node)\n",
    "        visited = set()\n",
    "        while queue:\n",
    "            cost, node = heapq.heappop(queue)\n",
    "\n",
    "            if node in visited:\n",
    "                continue\n",
    "            visited.add(node)\n",
    "\n",
    "            if node == 1:  # target node found\n",
    "                return cost\n",
    "\n",
    "            for neighbor, edge_cost in graph[node]:\n",
    "                if neighbor not in visited:\n",
    "                    heapq.heappush(queue, (cost + edge_cost, neighbor))\n",
    "\n",
    "        return -1  # if no path is found\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import Counter, defaultdict\n",
    "from heapq import heappop, heappush\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        adj = defaultdict(list)\n",
    "        lst = set()\n",
    "        lst.add(tuple(start))\n",
    "        lst.add(tuple(target))\n",
    "        for x1,y1,x2,y2,c in specialRoads:\n",
    "            adj[(x1,y1)].append(((x2,y2),c))\n",
    "            lst.add((x1,y1))\n",
    "            lst.add((x2,y2))\n",
    "        lst = list(lst)\n",
    "        for i in range(len(lst)):\n",
    "            for j in range(i):\n",
    "                x1,y1 = lst[i];x2,y2 = lst[j]\n",
    "                adj[(x1,y1)].append(((x2,y2),abs(x1-x2) + abs(y1 - y2)))\n",
    "                adj[(x2,y2)].append(((x1,y1),abs(x1-x2) + abs(y1 - y2)))\n",
    "        inf = float('inf')\n",
    "        dis = defaultdict(lambda:inf)\n",
    "        hp = [(0,tuple(start))]\n",
    "        dis[tuple(start)] = 0\n",
    "        while hp:\n",
    "            d,o = heappop(hp)\n",
    "            if d > dis[o]:continue\n",
    "            for nxt,c in adj[o]:\n",
    "                if dis[nxt] > c + d:\n",
    "                    dis[nxt] = c + d\n",
    "                    heappush(hp,(c + d,nxt))\n",
    "        return dis[tuple(target)]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], a: List[List[int]]) -> int:\n",
    "        x0, y0 = start\n",
    "        x00, y00 = target\n",
    "        g = defaultdict(list)\n",
    "        for x1, y1, x2, y2, cost in a:\n",
    "            g[(x1, y1)].append(((x2, y2), cost))\n",
    "            g[(x1, y1)].append(((x2, y2), abs(x1-x2)+abs(y1-y2)))\n",
    "            \n",
    "            g[(x0, y0)].append(((x1, y1), abs(x0-x1) + abs(y0-y1)))\n",
    "            g[(x2, y2)].append(((x00, y00), abs(x00-x2) + abs(y00-y2)))\n",
    "        \n",
    "        for i in range(len(a)):\n",
    "            for j in range(i+1, len(a)):\n",
    "                x1, y1, x2, y2,_ = a[i]\n",
    "                x3, y3, x4, y4,_ = a[j]\n",
    "                g[(x1, y1)].append(((x3, y3), abs(x1-x3)+abs(y1-y3)))\n",
    "                g[(x1, y1)].append(((x4, y4), abs(x1-x4)+abs(y1-y4)))\n",
    "                g[(x3, y3)].append(((x1, y1), abs(x1-x3)+abs(y1-y3)))\n",
    "                g[(x4, y4)].append(((x1, y1), abs(x1-x4)+abs(y1-y4)))   \n",
    "                g[(x2, y2)].append(((x3, y3), abs(x2-x3)+abs(y2-y3)))\n",
    "                g[(x2, y2)].append(((x4, y4), abs(x2-x4)+abs(y2-y4)))\n",
    "                g[(x3, y3)].append(((x2, y2), abs(x2-x3)+abs(y2-y3)))\n",
    "                g[(x4, y4)].append(((x2, y2), abs(x2-x4)+abs(y2-y4)))   \n",
    "        \n",
    "        \n",
    "        def DJ(start, end):\n",
    "            queue = [(0, start)]\n",
    "            visited = set()\n",
    "            distances = {start: 0}\n",
    "            while queue:\n",
    "                (cost, current) = heapq.heappop(queue)\n",
    "                if current in visited:\n",
    "                    continue\n",
    "                visited.add(current)\n",
    "                if current == end:\n",
    "                    return distances[current]\n",
    "                # 特殊路径\n",
    "                for neighbor, weight in g[current]:\n",
    "                    new_cost = distances[current] + weight\n",
    "                    new_cost1 = distances[current] + abs(current[0] - neighbor[0]) + abs(current[1] - neighbor[1])\n",
    "                    if neighbor not in distances or new_cost < distances[neighbor]:\n",
    "                        distances[neighbor] = new_cost\n",
    "                        heapq.heappush(queue, (new_cost, neighbor))\n",
    "\n",
    "            return math.inf\n",
    "        ans = DJ((start[0], start[1]), (target[0], target[1]))\n",
    "        return min(ans, abs(x0 - x00) + abs(y0-y00))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        cost = defaultdict(lambda :inf)\n",
    "        points = set()\n",
    "        for x1, y1, x2, y2, c in specialRoads:\n",
    "            cost[x1, y1, x2, y2] = min(cost[x1, y1, x2, y2], c, abs(x2 - x1) + abs(y2 - y1))\n",
    "            points.add((x1, y1))\n",
    "            points.add((x2, y2))\n",
    "        \n",
    "        sx, sy = start\n",
    "        tx, ty = target\n",
    "        points.add((sx, sy))\n",
    "        points.add((tx, ty))\n",
    "        \n",
    "        for x1, y1 in points:\n",
    "            for x2, y2 in points:\n",
    "                cost[x1, y1, x2, y2] = min(cost[x1, y1, x2, y2], abs(x2 - x1) + abs(y2 - y1))\n",
    "        \n",
    "        dis = defaultdict(lambda :inf)\n",
    "        dis[sx, sy] = 0\n",
    "        q = [(0, sx, sy)]\n",
    "\n",
    "        while q:\n",
    "            d, x, y = heapq.heappop(q)\n",
    "            if d > dis[x, y]:\n",
    "                continue\n",
    "                \n",
    "            for ch in points:\n",
    "                x2, y2 = ch\n",
    "                if d + cost[x, y, x2, y2] < dis[x2, y2]:\n",
    "                    dis[x2, y2] = d + cost[x, y, x2, y2]\n",
    "                    heapq.heappush(q, (dis[x2, y2], x2, y2))\n",
    "\n",
    "        return dis[tx, ty]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        g = DefaultDict(set)\n",
    "        m = DefaultDict(int)\n",
    "        s = set()\n",
    "        s.add(tuple(target))\n",
    "        for a,b,c,d,_ in specialRoads:\n",
    "            s.add((a,b))\n",
    "            s.add((c,d))\n",
    "        for a,b,c,d,cost in specialRoads:\n",
    "            g[tuple(start)].add((a,b, abs(start[0] - a) + abs(start[-1] - b)))\n",
    "            g[tuple(start)].add((c,d, abs(start[0] - c) + abs(start[-1] - d)))\n",
    "            g[(a,b)].add((c,d,cost))\n",
    "            #g[(c,d)].add((a,b,cost))\n",
    "            for x,y in s:\n",
    "                if (x,y) != (c,d):\n",
    "                    g[(a,b)].add((x,y,abs(x-a)+abs(y-b)))\n",
    "                if (x,y) != (a,b):\n",
    "                    g[(c,d)].add((x,y,abs(x-c)+abs(y-d)))\n",
    "        \n",
    "\n",
    "        pq = PriorityQueue()\n",
    "        pq.put((0,start[0],start[-1]))\n",
    "        m[(start[0],start[-1])] = 0\n",
    "        \n",
    "        while not pq.empty():\n",
    "            cost,x,y = pq.get()\n",
    "            for nx,ny,tcost in g[(x, y)]:\n",
    "                if (nx,ny) not in m or cost + tcost < m[(nx, ny)]:\n",
    "                    m[(nx, ny)] = cost + tcost\n",
    "                    pq.put((cost + tcost, nx, ny))\n",
    "        return m[(target[0], target[-1])]\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:\n",
    "        edge=collections.defaultdict(list)\n",
    "        point=set()\n",
    "        point.add(tuple(start))\n",
    "        point.add(tuple(target))\n",
    "        for x1,y1,x2,y2,d in specialRoads:\n",
    "            point.add((x1,y1))\n",
    "            point.add((x2,y2))\n",
    "            edge[(x1,y1)].append((x2,y2,d))\n",
    "        #print(point)\n",
    "        point=list(point)\n",
    "        m=len(point)\n",
    "        for i in range(m-1):\n",
    "            for j in range(i+1,m):\n",
    "                x1,y1=point[i]\n",
    "                x2,y2=point[j]\n",
    "                d=abs(x1-x2)+abs(y1-y2)\n",
    "                edge[(x1,y1)].append((x2,y2,d))\n",
    "                edge[(x2,y2)].append((x1,y1,d))\n",
    "        #print(edge)\n",
    "        find=set()\n",
    "        q=[(0,start[0],start[1])]\n",
    "        while q:\n",
    "            d,x,y=heapq.heappop(q)\n",
    "            #print(d,x,y)\n",
    "            if (x,y) in find:\n",
    "                continue\n",
    "            if x==target[0] and y==target[1]:\n",
    "                return d\n",
    "            find.add((x,y))\n",
    "            for a,b,dd in edge[(x,y)]:\n",
    "                heapq.heappush(q,(dd+d,a,b))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            try:\n",
    "                cnt += cost.pop()\n",
    "                cnt += cost.pop()\n",
    "                cost.pop()\n",
    "            except IndexError:\n",
    "                return cnt\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        res=[]\n",
    "        while cost:\n",
    "            res.append(cost.pop())\n",
    "            if cost:\n",
    "                res.append(cost.pop())\n",
    "            if cost:\n",
    "                cost.pop()\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse = True)\n",
    "        return sum(cost) - sum(cost[2::3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        n = len(cost)\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            if i % 3 == 2:\n",
    "                pass\n",
    "            else:\n",
    "                count += cost[i]\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        loop = len(cost)\n",
    "        if loop < 3:\n",
    "            return sum(cost)\n",
    "        else:\n",
    "            cost.sort()\n",
    "            \n",
    "            min_cost = 0\n",
    "            for i in range(loop // 3):\n",
    "                min_cost += cost.pop() + cost.pop()\n",
    "                cost.pop()\n",
    "\n",
    "                if len(cost) == 1:\n",
    "                    min_cost += cost.pop()\n",
    "                elif len(cost) == 2:\n",
    "                    min_cost += cost.pop() + cost.pop()\n",
    "        return min_cost    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        ans = 0\n",
    "        while len(cost) >= 3:\n",
    "            ans += cost.pop()\n",
    "            ans += cost.pop()\n",
    "            cost.pop()\n",
    "        if cost:\n",
    "            ans += sum(cost)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        sum = 0\n",
    "        for i in range(len(cost)):\n",
    "            if i % 3 != 2:\n",
    "                sum += cost[i]\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        n = len(cost)\n",
    "        if n < 3:\n",
    "            return sum(cost)\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            cnt += 1\n",
    "            if cnt == 3:\n",
    "                cnt = 0\n",
    "            else:\n",
    "                ans += cost[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        sum = 0\n",
    "        l = len(cost)\n",
    "        for i in range(l):\n",
    "            if i % 3 != 2:\n",
    "                sum += cost[i]\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        n = len(cost)\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            cnt += 1\n",
    "            if cnt == 3:\n",
    "                cnt = 0\n",
    "            else:\n",
    "                ans += cost[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        cnt = 0\n",
    "        while cost:\n",
    "            try:\n",
    "                a = cost.pop()\n",
    "                cnt += a\n",
    "                b = cost.pop()\n",
    "                cnt += b\n",
    "                cost.pop()\n",
    "            except IndexError:\n",
    "                return cnt\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        cnt = 0\n",
    "        while cost:\n",
    "            try:\n",
    "                cnt += cost.pop()\n",
    "                cnt += cost.pop()\n",
    "                cost.pop()\n",
    "            except IndexError:\n",
    "                return cnt\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "      cost.sort(reverse=True)\n",
    "      return sum([cost[i] for i in range(len(cost)) if (i+1) % 3 != 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        ans = 0\n",
    "        i = len(cost)-1\n",
    "        while i>=0:\n",
    "            ans+=cost[i]\n",
    "            i-=1\n",
    "            if i>=0:\n",
    "                ans+=cost[i]\n",
    "            i-=2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost = sorted(cost)[::-1]\n",
    "        return sum(cost) - sum(cost[2::3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        res=0\n",
    "        now=0\n",
    "        for i in range(0,len(cost)):\n",
    "            if now==2:\n",
    "                now=0\n",
    "                continue\n",
    "            now+=1\n",
    "            res+=cost[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        return sum(cost[::3] + cost[1::3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost2 = sorted(cost)\n",
    "        num2 = len(cost2)//3\n",
    "        for i in range(num2):\n",
    "            cost2[-3-3*i] = 0\n",
    "        a = 0\n",
    "        for i in cost2:\n",
    "            a += i\n",
    "        return a\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        sorted_list = sorted(cost, reverse=True)\n",
    "        total_sum = 0\n",
    "        i = 0\n",
    "\n",
    "        while i < len(sorted_list):\n",
    "            total_sum += sorted_list[i]\n",
    "            i += 1\n",
    "\n",
    "            if i < len(sorted_list):\n",
    "                total_sum += sorted_list[i]\n",
    "                i += 2  # 跳过下一个元素\n",
    "\n",
    "        return total_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        return sum(cost[-i-1] for i in range(len(cost)) if i % 3 != 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "      cost.sort(reverse=True)\n",
    "      n = len(cost)\n",
    "      return sum([cost[i] for i in range(n) if (i+1) % 3 != 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse = True)\n",
    "        t = 0\n",
    "        for i in range(0,len(cost),3):\n",
    "            if len(cost[i:]) < 3:\n",
    "                t+=sum(cost[i:])\n",
    "            else:\n",
    "                t+=sum(cost[i:i+2])\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(key = lambda x: -x)\n",
    "        res = 0\n",
    "        n = len(cost)\n",
    "        for i in range(n):\n",
    "            if i % 3 != 2:\n",
    "                res += cost[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost) -> int:\n",
    "        n = len(cost)\n",
    "        sum_ = 0\n",
    "        cost.sort(reverse=True)\n",
    "        while n>0:\n",
    "            if n <= 2:\n",
    "                sum_ += sum(cost)\n",
    "                break\n",
    "            count = cost[0] + cost[1]\n",
    "            for i in range(2,n):\n",
    "                if cost[1] >= cost[i]:\n",
    "                    cost.pop(i)\n",
    "                    cost.pop(0)\n",
    "                    cost.pop(0)\n",
    "                    n -= 3\n",
    "                    sum_ += count\n",
    "                    break\n",
    "        return sum_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        ans = 0\n",
    "        price = sorted(cost, reverse=True)\n",
    "        for i in range(n):\n",
    "            if (i + 1) % 3 != 0:\n",
    "                ans += price[i]\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        x=[]\n",
    "        s=0\n",
    "        for i in sorted(cost,reverse=True):\n",
    "            x.append(i)\n",
    "            if len(x)<=2:\n",
    "                s+=i\n",
    "            elif len(x)>2:\n",
    "                x=[]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cost.sort(reverse = True)\n",
    "        ans = sum(cost[::3]) + sum(cost[1::3])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        cost=cost[::-1]\n",
    "        ans=0\n",
    "        for i in range(len(cost)):\n",
    "            if (i+1)%3!=0:\n",
    "                ans+=cost[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        a=0\n",
    "        cost=sorted(cost,reverse=True)\n",
    "        i=0\n",
    "        while i<len(cost):\n",
    "            a+=cost[i]\n",
    "            i+=1\n",
    "            if (i+1)%3==0:i+=1\n",
    "        return a\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        n = len(cost)\n",
    "        i = 1\n",
    "        ans = 0\n",
    "        while i-1 < n:\n",
    "            if i % 3 != 0:\n",
    "                ans += cost[i-1]\n",
    "            i += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(key = lambda x: -x)\n",
    "        ans = 0\n",
    "        n = len(cost)\n",
    "        for i in range(n):\n",
    "            if i % 3 != 2:\n",
    "                ans += cost[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        k = 0 \n",
    "        sum1 = 0\n",
    "        for i in range(len(cost)):\n",
    "            k += 1\n",
    "            if k == 3:\n",
    "                k = 0\n",
    "                continue\n",
    "            else:\n",
    "                sum1 += cost[i]\n",
    "        return sum1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        i, j, ans = 0, 1, 0\n",
    "        cost.sort(reverse=True)\n",
    "        n = len(cost)\n",
    "        if n < 3:\n",
    "            return sum(cost)\n",
    "        while j < n:\n",
    "            ans += cost[i] + cost[j]\n",
    "            i += 3\n",
    "            j += 3\n",
    "        if i < n:\n",
    "            ans += cost[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        return sum(cost[::3]) + sum(cost[1::3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        if len(cost)<=2:\n",
    "            return sum(cost)\n",
    "        c=0\n",
    "        s=0\n",
    "        for x in cost:\n",
    "           if c==2:\n",
    "               c=0\n",
    "               continue\n",
    "           s+=x\n",
    "           c+=1\n",
    "        return s   \n",
    "           \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost = sorted(cost,reverse=True)\n",
    "        ans = 0\n",
    "        for i in range(len(cost)):\n",
    "            if (i + 1) % 3:\n",
    "                ans += cost[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        sum = 0\n",
    "        count = 0\n",
    "        for i in cost:\n",
    "            if count != 2:\n",
    "                sum += i\n",
    "                count += 1\n",
    "            else:\n",
    "                count = 0\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        j, ans = 1, 0\n",
    "        n = len(cost)\n",
    "        if n < 3:\n",
    "            return sum(cost)\n",
    "        cost.sort(reverse=True)\n",
    "        while j < n:\n",
    "            ans += cost[j - 1] + cost[j]\n",
    "            j += 3\n",
    "        if j == n:\n",
    "            ans += cost[j - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        # 按价格逆序排列糖果，去掉3的整数倍的糖果\n",
    "        cost.sort(reverse = True)\n",
    "        for i in range(2,len(cost),3):\n",
    "            cost[i] = 0\n",
    "        return sum(cost)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        _len = len(cost)\n",
    "        if _len == 2:\n",
    "            return cost[-1]+cost[0]\n",
    "        elif _len ==1:\n",
    "            return cost[0]\n",
    "        cost.sort()\n",
    "        cost = cost[::-1]\n",
    "        ret = 0\n",
    "        nb = []\n",
    "        flag = True\n",
    "        for i in range(_len):\n",
    "            if len(nb)<2 and flag:\n",
    "                nb.append(cost[i])\n",
    "            flag = True\n",
    "            if len(nb) ==2 or i==_len-1:\n",
    "                ret+=sum(nb)\n",
    "                nb = []\n",
    "                flag = False\n",
    "        return ret\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cost.sort(key = lambda x: -x)\n",
    "        n = len(cost)\n",
    "        for i in range(n):\n",
    "             if i % 3 != 2:\n",
    "                ans += cost[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        ans=0\n",
    "        cost.sort(reverse=True)\n",
    "        for i in range(0,len(cost),3):\n",
    "            if i+1 in range(len(cost)):\n",
    "                ans+=cost[i]+cost[i+1]\n",
    "            else:\n",
    "                ans+=cost[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost):\n",
    "        cost.sort(reverse = True)\n",
    "        return sum(cost[::3])  + sum(cost[1::3])      \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        ans=0\n",
    "        mark=0\n",
    "        cost.sort(reverse=True)\n",
    "        for c in cost:\n",
    "            if mark==2:\n",
    "                mark=0\n",
    "                continue\n",
    "            ans+=c\n",
    "            mark+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        ans = 0\n",
    "        while len(cost):\n",
    "            if len(cost) > 2:\n",
    "                ans += cost[-1] + cost[-2]\n",
    "                cost = cost[0:-3]\n",
    "            else:\n",
    "                ans += sum(cost)\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        k = 0 \n",
    "        sum1 = 0\n",
    "        for i in range(len(cost)):\n",
    "            k += 1\n",
    "            if k == 3:\n",
    "                k = 0\n",
    "                continue\n",
    "            else:\n",
    "                sum1 += cost[i]\n",
    "        return sum1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(key = lambda x: -x)\n",
    "        res = 0\n",
    "        n = len(cost)\n",
    "        for i in range(n):\n",
    "            if i % 3 != 2:\n",
    "                res += cost[i]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(key = lambda x: -x)\n",
    "        res = 0\n",
    "        n = len(cost)\n",
    "        for i in range(n):\n",
    "            if i % 3 != 2:\n",
    "                res += cost[i]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost=sorted(cost,reverse=True)\n",
    "        aa=0\n",
    "        for i in range(len(cost)):\n",
    "            if (i+1)%3!=0:\n",
    "                aa+=cost[i]\n",
    "        return aa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "\n",
    "        cost.sort(reverse=True)\n",
    "\n",
    "        result = 0\n",
    "        pos = 0\n",
    "        while pos + 3 <= len(cost):\n",
    "            result += (cost[pos] + cost[pos + 1])\n",
    "            pos += 3\n",
    "\n",
    "        if pos < len(cost):\n",
    "            result += sum(cost[pos:])\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        i,n,ans = 0,len(cost),0\n",
    "        while i<n:\n",
    "            if i+2<n:\n",
    "                ans += (cost[i]+cost[i+1])\n",
    "                i += 3\n",
    "            else:\n",
    "                ans += sum(cost[i:])\n",
    "                i = n\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        if(len(cost)==1 or len(cost)==2):\n",
    "            return sum(cost)\n",
    "        else:\n",
    "            k=len(cost)//3\n",
    "            s=sum(cost)\n",
    "            cost.sort()\n",
    "            for i in range(k):\n",
    "                s -= cost[-3*(i+1)]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "\n",
    "        summ = 0\n",
    "\n",
    "        a, remain = len(cost)//3, len(cost)%3\n",
    "\n",
    "        for i in range(a):\n",
    "            summ += cost[3*i] + cost[3*i+1]\n",
    "        \n",
    "        if remain==1:\n",
    "            summ+=cost[-1]\n",
    "        elif remain==2:\n",
    "            summ+=cost[-1]+cost[-2]\n",
    "\n",
    "        return summ\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        if len(cost) <= 2:\n",
    "            return sum(cost)\n",
    "        \n",
    "        cost.sort(reverse=True)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(0, len(cost), 3):\n",
    "            if i < len(cost):\n",
    "                res += cost[i]\n",
    "            if i + 1 < len(cost):\n",
    "                res += cost[i+1]\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(key = lambda x: -x)\n",
    "        res = 0\n",
    "        n = len(cost)\n",
    "        for i in range(n):\n",
    "            if i % 3 != 2:\n",
    "                res += cost[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        return sum(cost[::3]) + sum(cost[1::3])\n",
    "        # k = 0 \n",
    "        # sum1 = 0\n",
    "        # for i in range(len(cost)):\n",
    "        #     k += 1\n",
    "        #     if k == 3:\n",
    "        #         k = 0\n",
    "        #         continue\n",
    "        #     else:\n",
    "        #         sum1 += cost[i]\n",
    "        # return sum1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        j = len(cost)-1\n",
    "        c = 0\n",
    "        r = 0\n",
    "        while j>= 0:\n",
    "            if r<2:\n",
    "                c += cost[j]\n",
    "                r+=1\n",
    "                j-=1\n",
    "            else:\n",
    "                j-=1\n",
    "                r=0\n",
    "        return c\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        return sum(cost[i] for i in range(len(cost)) if i % 3 != 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        n=len(cost)\n",
    "        count=0\n",
    "        for i in range(2,n,3):\n",
    "            count+=cost[i]\n",
    "        return sum(cost)-count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        cost.sort(reverse=True)\n",
    "        while i < len(cost):\n",
    "            ans += cost[i]\n",
    "            if i + 1 < len(cost):\n",
    "                ans += cost[i + 1]\n",
    "            i += 3\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        cnt = len(cost)\n",
    "        cnt_more_than_three = cnt // 3\n",
    "        cnt_mod = cnt % 3\n",
    "        min_cost = 0\n",
    "        for i in range(cnt_more_than_three, 0, -1):\n",
    "            min_cost += (cost[3 * i + cnt_mod - 1] + cost[3 * i + cnt_mod - 2])\n",
    "        if cnt_mod == 2:\n",
    "            min_cost += (cost[0] + cost[1])\n",
    "        elif cnt_mod == 1:\n",
    "            min_cost += cost[0]\n",
    "        return min_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        n = len(cost)\n",
    "        ans = i = 0\n",
    "        while i < n:\n",
    "            ans += cost[i]\n",
    "            i += 1\n",
    "            if i < n:\n",
    "                ans += cost[i]\n",
    "            i += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost = sorted(cost, key=lambda x: -x)\n",
    "        res = sum(cost[0::3]) + sum(cost[1::3])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        k = 0 \n",
    "        sum1 = 0\n",
    "        for i in range(len(cost)):\n",
    "            k += 1\n",
    "            if k == 3:\n",
    "                k = 0\n",
    "                continue\n",
    "            else:\n",
    "                sum1 += cost[i]\n",
    "        return sum1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort()\n",
    "        res=0\n",
    "        i=len(cost)-1\n",
    "        while i>=1:\n",
    "            res+=cost[i]+cost[i-1]\n",
    "            i-=3\n",
    "        if i==0:\n",
    "            res+=cost[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(key = lambda x : -x);\n",
    "        res =0;\n",
    "        n = len(cost);\n",
    "        for i in range(n):\n",
    "            if i%3!=2:\n",
    "                res += cost[i];\n",
    "        return res;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "      if len(cost) <= 2: \n",
    "        return sum(cost)\n",
    "\n",
    "      cost.sort(reverse=True)\n",
    "      res = 0\n",
    "      \n",
    "      for i in range(len(cost)):\n",
    "        if (i+1)%3:\n",
    "          res += cost[i]\n",
    "        \n",
    "      return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumCost(self, cost: List[int]) -> int:\n",
    "#         n = len(cost)\n",
    "#         i = 0\n",
    "#         cost.sort(reverse=True)\n",
    "#         total=0\n",
    "#         print(cost)\n",
    "#         if n <= 2:\n",
    "#             return sum(cost)\n",
    "#         while i<n:\n",
    "#             total+=cost[i]\n",
    "#             if i+1<=n-1:\n",
    "#                 total+=cost[i+1]\n",
    "#             i+=3\n",
    "#         return total\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        n=len(cost)\n",
    "        amount=0\n",
    "        if n<=2:\n",
    "            amount=sum(cost)\n",
    "            return amount\n",
    "        i=0\n",
    "        while i<n:\n",
    "            amount+=cost[i]\n",
    "            if i+1<=n-1:\n",
    "                amount+=cost[i+1]\n",
    "            i+=3\n",
    "        return amount\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(reverse=True)\n",
    "        # 思路是排序之后从先买最贵的两个，然后面肥获取次之贵的糖果\n",
    "        n = len(cost)\n",
    "        if n <= 2:\n",
    "            return sum(cost)\n",
    "        answer = 0\n",
    "        while cost and len(cost) > 2:\n",
    "            i = 2\n",
    "            while cost and i < len(cost):\n",
    "                a = cost[i - 1]\n",
    "                b = cost[i - 2]\n",
    "                answer += (a + b)\n",
    "                if cost[i] <= min(a, b):\n",
    "                    cost.pop(i)\n",
    "                    cost.pop(1)\n",
    "                    cost.pop(0)\n",
    "        if cost:\n",
    "            answer += sum(cost)\n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cost.sort(reverse = True)\n",
    "        for i in range(len(cost)):\n",
    "            if (i+1) % 3 == 0 :\n",
    "                continue\n",
    "            ans += cost[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        i, j, ans = 0, 1, 0\n",
    "        n = len(cost)\n",
    "        if n < 3:\n",
    "            return sum(cost)\n",
    "        cost.sort(reverse=True)\n",
    "        while j < n:\n",
    "            ans += cost[i] + cost[j]\n",
    "            i += 3\n",
    "            j += 3\n",
    "        if i < n:\n",
    "            ans += cost[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(key=lambda x:-x)\n",
    "        res=0\n",
    "        n=len(cost)\n",
    "        for i in range(n):\n",
    "            if i%3!=2:\n",
    "                res+=cost[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        _len = len(cost)\n",
    "        if _len == 2:\n",
    "            return cost[-1]+cost[0]\n",
    "        elif _len ==1:\n",
    "            return cost[0]\n",
    "        cost.sort()\n",
    "        cost = cost[::-1]\n",
    "        ret = 0\n",
    "        nb = []\n",
    "        flag = True\n",
    "        for i in range(_len):\n",
    "            if len(nb)<2 and flag:\n",
    "                nb.append(cost[i])\n",
    "            flag = True\n",
    "            if len(nb) ==2 or i==_len-1:\n",
    "                ret+=sum(nb)\n",
    "                nb = []\n",
    "                flag = False\n",
    "        return ret\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        queue = [-num for num in cost]\n",
    "        heapq.heapify(queue)\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            if len(queue) <= 2:\n",
    "                for _ in range(len(queue)):\n",
    "                    ans += -heapq.heappop(queue)\n",
    "            else:\n",
    "                for _ in range(2):\n",
    "                    ans += -heapq.heappop(queue)\n",
    "                heapq.heappop(queue)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumCost(self, cost: List[int]) -> int:\n",
    "#         cost=sorted(cost)\n",
    "#         ans=0\n",
    "#         while cost:\n",
    "#             ans+=cost.pop()\n",
    "#             if cost:\n",
    "#                 ans+=cost.pop()\n",
    "#             if cost:\n",
    "#                 cost.pop()\n",
    "#         return ans\n",
    "\n",
    "### 官：贪心\n",
    "class Solution:\n",
    "    def minimumCost(self, cost: List[int]) -> int:\n",
    "        cost.sort(key = lambda x: -x)\n",
    "        res = 0\n",
    "        n = len(cost)\n",
    "        for i in range(n):\n",
    "            if i % 3 != 2:\n",
    "                res += cost[i]\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        ans=0\n",
    "        if 1:\n",
    "            for i in range(n//2,0,-1):\n",
    "                if s[i]!=s[i-1]:\n",
    "                    ans+=i\n",
    "            for i in range(n//2+1,n):\n",
    "                if s[i]!=s[i-1]:\n",
    "                    ans+=n-i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        ans = 0\n",
    "        for i in range(N-1):\n",
    "            if s[i] != s[i+1]:\n",
    "                ans += min(i+1, N-(i+1))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        return sum(min(i, len(s) - i) for i, (x, y) in enumerate(pairwise(s), 1) if x != y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            if s[i-1] != s[i]:\n",
    "                # flip [0...i) or flip [i...n)\n",
    "                res += min(i, n - i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        '''\n",
    "        从字符串左端或右端进行一次操作的成本是相同的(每次转变i个字符的成本为i)，\n",
    "        决定将s全变为1还是全变为0要看字符串最中间的字符是1还是0(因为变它所需的成本最高)。\n",
    "        当s.length为奇数时，就由最中间的字符决定；当s.length为偶数时，由中间的两个字符决定，同0变0，同1变1，一0一1则变哪个都可以(是等价的)。\n",
    "        以中间的数分别往左右两边统计要操作的次数，记录当前的状态(0或1)，再加上其成本(对应的下标)，并更新状态。\n",
    "        '''\n",
    "\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        #if n % 2 == 0:\n",
    "        mid = int(n / 2)        #int是向下取整，当n为奇数时，比如n = 5，int(n / 2) = 2，恰好为中间的那一位，因此无需分类讨论\n",
    "        '''\n",
    "        if s[mid] == s[mid + 1]:\n",
    "            state = s[mid]\n",
    "        else:\n",
    "            state = s[mid]\n",
    "        '''\n",
    "        state = s[mid]\n",
    "        t = state\n",
    "        i = mid - 1\n",
    "        while i >= 0:\n",
    "            if s[i] != t:\n",
    "                res += i + 1\n",
    "                t = s[i]\n",
    "            i -= 1\n",
    "        t = state\n",
    "        i = mid + 1\n",
    "        while i < n:\n",
    "            if s[i] != t:\n",
    "                res += n - i\n",
    "                t = s[i]\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        \n",
    "        i, j = 0, N - 1\n",
    "        res = 0\n",
    "        \n",
    "        while i < j:\n",
    "            if s[i] == s[i + 1]:\n",
    "                i += 1\n",
    "            elif s[j] == s[j - 1]:\n",
    "                j -= 1\n",
    "            else:\n",
    "                if i + 1 <= N - j:\n",
    "                    i += 1\n",
    "                    res += i\n",
    "                else:\n",
    "                    res += N - j\n",
    "                    j -= 1\n",
    "            \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        min1=0\n",
    "        for i in range(1,n):\n",
    "            if s[i-1]!=s[i]:\n",
    "                min1+=min(i,n-i)\n",
    "        return min1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        \n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(s) - 1):\n",
    "            if s[i] != s[i + 1]:\n",
    "                res += min(i + 1, len(s) - 1 - i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "      re = 0\n",
    "      n = len(s)\n",
    "      for i in range(1,n):\n",
    "        if(s[i] != s[i-1]):\n",
    "          re += min(i,n-i)\n",
    "      return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        return sum(min(i, len(s) - i) for i, (x, y) in enumerate(pairwise(s), 1) if x != y)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i-1] != s[i]:\n",
    "                ans += min(i, len(s) - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        return sum(min(i,len(s)-i) for i,(x,y) in enumerate(pairwise(s),1) if x!=y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        #copy 0x3\n",
    "        return sum(min(i,len(s)-i) for i,(x,y) in enumerate(pairwise(s),1) if x != y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        ans = 0\n",
    "        for i in range(N-1):\n",
    "            if s[i] != s[i+1]:\n",
    "                ans += min(i+1, N-(i+1))\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:   \n",
    "        n = len(s)\n",
    "        CNT0 = CNT1 = 0\n",
    "        for i in range(n - 1, n//2 - (n+1) % 2, -1):\n",
    "            if s[i] == \"0\":\n",
    "                CNT0, CNT1 = min(CNT0, CNT1 + n - 1 - i), min(CNT1 + 2*(n-i) - 1, CNT0 + n - i)\n",
    "            else:\n",
    "                CNT0, CNT1 = min(CNT0 + 2*(n-i) - 1, CNT1 + n - i), min(CNT0 + n - 1 - i, CNT1)\n",
    "        \n",
    "        cnt0 = cnt1 = 0        \n",
    "        for i in range(n//2):\n",
    "            if s[i] == \"0\":\n",
    "                cnt0, cnt1 = min(cnt0, cnt1 + i), min(cnt1 + 2 * i + 1, cnt0 + i + 1)\n",
    "            else:\n",
    "                cnt0, cnt1 = min(cnt1 + i + 1, cnt0 + 2 * i + 1), min(cnt0 + i, cnt1)\n",
    "        \n",
    "        if n % 2 == 0:\n",
    "            return min(cnt0 + CNT0, cnt1 + CNT1)\n",
    "        elif s[n//2] == \"0\":\n",
    "            return min(cnt0 + CNT0, cnt1 + CNT1 + n - 1)\n",
    "        else:\n",
    "            return min(cnt0 + CNT0 + n - 1, cnt1 + CNT1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] != s[i-1]:\n",
    "                res += min(i,len(s)-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i,(x,y) in enumerate(pairwise(s),1):\n",
    "            if x != y :\n",
    "                ans += min(i,len(s)-i)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        idx=s[0]\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if s[i]!=idx:\n",
    "                res+=min(i,n-i)\n",
    "                idx=s[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        for i in range(n-1):\n",
    "            if s[i] != s[i+1]:\n",
    "                res += min(i+1, n-(i+1))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "      last=s[0]\n",
    "      c=0\n",
    "      n=len(s)\n",
    "      for i,ch in enumerate(s):\n",
    "        if ch!=last:\n",
    "          c+=min(i,n-i)\n",
    "        last=ch\n",
    "      return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] != s[i-1]:\n",
    "                ans += min(i, n-i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        return sum(min(i, len(s) - i) for i, (x, y) in enumerate(pairwise(s), 1) if x != y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def go(target):\n",
    "            ret = 0\n",
    "            flip = False\n",
    "            for i in range(n >> 1, n):\n",
    "                if (s[i] == target) != flip:\n",
    "                    flip ^= True\n",
    "                    ret += n - i\n",
    "            flip = False\n",
    "            for i in range(n // 2 - 1, -1, -1): \n",
    "                if (s[i] == target) != flip:\n",
    "                    flip ^= True\n",
    "                    ret += i + 1\n",
    "            return ret\n",
    "        return min(go('0'), go('1'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(1, n):                        # hit a 01 or 10, must reverse front or back\n",
    "            if s[i] != s[i - 1]:\n",
    "                res += min((i - 1 + 1), (n - i))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        ans, n = 0, len(s)\n",
    "        for i in range(n - 1):\n",
    "            if s[i] != s[i + 1]:\n",
    "                ans += min(i + 1, n - i - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        return sum(min(i, len(s) - i) for i, (x, y) in enumerate(pairwise(s), 1) if x != y)\n",
    "        # 如果s[i-1] != s[i]，必须反转，成本为min(i,n-i)\n",
    "        # 从左到右遍历一次，s[i]左边的字符已经相等，s[i]右边的相邻字符，反转前不同的，反转后仍然不同。所以要继续反转。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        return sum(min(i, n - i) for i in range(1, n) if s[i] != s[i - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i > 0 and s[i] != s[i - 1]:\n",
    "                ans += min(i, n - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            if s[i] != s[i - 1]:\n",
    "                res += min(i, n - i)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i, (a, b) in enumerate(zip(s[:-1], s[1:])):\n",
    "            if a != b:\n",
    "                ans += min(i + 1, len(s) - i - 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:   \n",
    "        n = len(s)\n",
    "        CNT0 = CNT1 = 0\n",
    "        for i in range(n - 1, n//2 - (n+1) % 2, -1):\n",
    "            if s[i] == \"0\":\n",
    "                CNT0, CNT1 = min(CNT0, CNT1 + n - 1 - i), min(CNT1 + 2*(n-i) - 1, CNT0 + n - i)\n",
    "            else:\n",
    "                CNT0, CNT1 = min(CNT0 + 2*(n-i) - 1, CNT1 + n - i), min(CNT0 + n - 1 - i, CNT1)\n",
    "        \n",
    "        cnt0 = cnt1 = 0        \n",
    "        for i in range(n//2):\n",
    "            if s[i] == \"0\":\n",
    "                cnt0, cnt1 = min(cnt0, cnt1 + i), min(cnt1 + 2 * i + 1, cnt0 + i + 1)\n",
    "            else:\n",
    "                cnt0, cnt1 = min(cnt1 + i + 1, cnt0 + 2 * i + 1), min(cnt0 + i, cnt1)\n",
    "        \n",
    "        if n % 2 == 0:\n",
    "            return min(cnt0 + CNT0, cnt1 + CNT1)\n",
    "        elif s[n//2] == \"0\":\n",
    "            return min(cnt0 + CNT0, cnt1 + CNT1 + n - 1)\n",
    "        else:\n",
    "            return min(cnt0 + CNT0 + n - 1, cnt1 + CNT1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        return sum(min(i, len(s) - i) for i, (x, y) in enumerate(pairwise(s), 1) if x != y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        return sum(min(i, len(s) - i) for i, (x, y) in enumerate(pairwise(s), 1) if x != y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        count = 0\n",
    "        for i, (x, y) in enumerate(pairwise(s), 1):\n",
    "            if x!=y:\n",
    "                count += min(i, len(s) - i)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        len = s.__len__()\n",
    "        if len == 1:\n",
    "            return 0\n",
    "        half_id = len // 2\n",
    "        count = 0\n",
    "        for (id,c) in enumerate(s[0:half_id-1]):\n",
    "            if c != s[id + 1]:\n",
    "                count += id + 1\n",
    "                print(\"+\",id,c,count)\n",
    "        for (id,c) in enumerate(reversed(s[half_id+1:])):\n",
    "            if c != s[-id-2]:\n",
    "                count += id + 1\n",
    "                print(\"-\",id,c,count)\n",
    "        if s[half_id] != s[half_id-1]:\n",
    "            count += half_id        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        i,j=0,len(s)-1\n",
    "        count=0\n",
    "        while(i<j):\n",
    "            if s[i]!=s[i+1]:\n",
    "                count+=i+1\n",
    "            i+=1\n",
    "            if(i==j):\n",
    "                break\n",
    "            if s[j]!=s[j-1]:\n",
    "                count+=len(s)-j\n",
    "            j-=1\n",
    "        if(s[i]!=s[j]):\n",
    "            return count+i\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        N = len(s)\n",
    "        ans = 0\n",
    "        for i in range(N-1):\n",
    "            if s[i] != s[i+1]:\n",
    "                ans += min(i+1, N-(i+1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            if s[i] != s[i + 1]:\n",
    "                ans += min(i + 1, n - i - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        def getres(tar,s):\n",
    "            n = len(s)\n",
    "            res = 0\n",
    "            left = n //2 -1\n",
    "            right = n //2\n",
    "            flag = 0\n",
    "            while left >=0:\n",
    "                if flag % 2 != 0:\n",
    "                    if s[left] == '0':\n",
    "                        temp = '1'\n",
    "                    else:\n",
    "                        temp = '0'\n",
    "                else:\n",
    "                    if s[left] == '0':\n",
    "                        temp = '0'\n",
    "                    else:\n",
    "                        temp = '1'\n",
    "                if temp != tar:\n",
    "                    flag += 1\n",
    "                    res += left+1\n",
    "                left -= 1\n",
    "            flag = 0\n",
    "            while right<n:\n",
    "                if flag % 2 != 0:\n",
    "                    if s[right] == '0':\n",
    "                        temp = '1'\n",
    "                    else:\n",
    "                        temp = '0'\n",
    "                else:\n",
    "                    if s[right] == '0':\n",
    "                        temp = '0'\n",
    "                    else:\n",
    "                        temp = '1'\n",
    "                if temp != tar:\n",
    "                    flag += 1\n",
    "                    res += n-right\n",
    "                right += 1\n",
    "            return res\n",
    "        return min(getres('1',s),getres('0',s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        L = len(s)\n",
    "        return sum(min(i,L-i) for i in range(1,L) if s[i-1]!=s[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            while l < r and s[l] == s[l + 1]:\n",
    "                l += 1\n",
    "            while l < r and s[r] == s[r - 1]:\n",
    "                r -= 1\n",
    "            if l >= r:\n",
    "                return ans\n",
    "            else:\n",
    "                lc, rc = l + 1, n - r\n",
    "                if lc <= rc:\n",
    "                    ans += lc\n",
    "                    l += 1\n",
    "                else:\n",
    "                    ans += rc\n",
    "                    r -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        len = s.__len__()\n",
    "        if len == 1:\n",
    "            return 0\n",
    "        half_id = len // 2\n",
    "        count = 0\n",
    "        for (id,c) in enumerate(s[0:half_id-1]):\n",
    "            if c != s[id + 1]:\n",
    "                count += id + 1\n",
    "                print(\"+\",id,c,count)\n",
    "        for (id,c) in enumerate(reversed(s[half_id+1:])):\n",
    "            if c != s[-id-2]:\n",
    "                count += id + 1\n",
    "                print(\"-\",id,c,count)\n",
    "        if s[half_id] != s[half_id-1]:\n",
    "            count += half_id        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        m = (n+1)//2\n",
    "        left = 0\n",
    "        for i in range(1, m):\n",
    "            if s[i]!=s[i-1]:\n",
    "                left += i\n",
    "        right = 0\n",
    "        for i in range(n-2, m-1, -1):\n",
    "            if s[i]!=s[i+1]:\n",
    "                right += n-i-1\n",
    "        if m < n and s[m-1] != s[m]:\n",
    "            right += n-m\n",
    "        return left+right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [0] * n\n",
    "        for i in range(1, n):\n",
    "            if s[i] == s[i - 1]:\n",
    "                f[i] = f[i - 1]\n",
    "            else:\n",
    "                f[i] = f[i - 1] + min(i, n - i)\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        neg = [0] * (n)\n",
    "\n",
    "        r = s[-1]\n",
    "        now = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] != r:\n",
    "                now += (n-i-1)\n",
    "            r = s[i]\n",
    "            neg[i] = now\n",
    "\n",
    "        ans = neg[0]\n",
    "        now = 0\n",
    "        l = s[0]\n",
    "        for i, ch in enumerate(s):\n",
    "            if l != ch:\n",
    "                now += i\n",
    "            l = ch\n",
    "            ans = min(ans, now + neg[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        a = [sum(1 for _ in g[1]) for g in groupby(s)]\n",
    "        f = lambda a: accumulate(accumulate(a, initial=0), initial=0)\n",
    "        b = list(f(reversed(a)))\n",
    "        return min(i + b.pop() for i in f(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        a = [sum(1 for _ in g[1]) for g in groupby(s)]\n",
    "        f = lambda a: accumulate(accumulate(a, initial=0), initial=0)\n",
    "        return min(map(sum, zip(reversed(tuple(f(reversed(a)))), f(a))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        left=[]\n",
    "        right=[]\n",
    "        idx=s[0]\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if s[i]!=idx:\n",
    "                \n",
    "                res+=min(i,n-i)\n",
    "                left.append(i)\n",
    "                right.append(n-i)\n",
    "                idx=s[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "                    \n",
    "                    n = len(s)\n",
    "                    left = [inf] * (n)\n",
    "                    right = [inf] * (n )\n",
    "                    left[0] = 0\n",
    "                    right[n-1] = 0\n",
    "                    for i in range(n- 1):\n",
    "                        if s[i] == s[i+1]:left[i+1] = left[i]\n",
    "                        else:left[i+1] = left[i]+ i + 1\n",
    "                    for i in range(n-1,0,-1):\n",
    "                        if s[i] == s[i-1]:right[i-1] = right[i]\n",
    "                        else:right[i - 1] = n - i + right[i]\n",
    "                    ans = inf\n",
    "                    for i in range(n):\n",
    "                        if i + 1 < n and s[i] == s[i+1]:\n",
    "                            ans = min(ans,left[i]+right[i+1])\n",
    "                        ans = min(ans,left[i] + right[i])\n",
    "                    \n",
    "                    return min(ans,left[n-1],right[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        \n",
    "        L = len(s)\n",
    "        dp1 = [0]*L\n",
    "        dp2 = [0]*L\n",
    "        for i in range(1,L):\n",
    "            dp1[i] = dp1[i-1]+i*(s[i]!=s[i-1])\n",
    "            j = L-1-i\n",
    "            dp2[j] = dp2[j+1]+(L-1-j)*(s[j]!=s[j+1])\n",
    "            \n",
    "        return min(dp1[i]+dp2[i] for i in range(L))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        # 动态规划\n",
    "        # 设置四行dp数组\n",
    "        # pre0, pre1, post0, post1\n",
    "        # 含义分别是，包含本位置的情况下把前面变成全0/1，后面变成全0/1的成本\n",
    "        n = len(s)\n",
    "        INF = 0xffffffff\n",
    "        pre0 = [INF for _ in range(n)]\n",
    "        pre1 = [INF for _ in range(n)]\n",
    "        post0 = [INF for _ in range(n)]\n",
    "        post1 = [INF for _ in range(n)]\n",
    "\n",
    "        if s[0] == '0':\n",
    "            pre0[0],pre1[0] = 0,1\n",
    "        else:\n",
    "            pre0[0],pre1[0] = 1,0\n",
    "        for i in range(1, n):\n",
    "            if s[i] == '0':            \n",
    "                # 要么不反转，它的费用可以直接接在pre0后面,或者选择反转前0~i-1个1,消耗为i\n",
    "                pre0[i] = min(pre0[i], pre0[i-1], pre1[i-1] + i)\n",
    "                pre1[i] = min(pre1[i], pre0[i-1] + i + 1) # 在前面全为0的基础上反转\n",
    "            elif s[i] == '1':\n",
    "                pre0[i] = min(pre0[i], pre1[i-1] + i + 1)\n",
    "                pre1[i] = min(pre1[i], pre1[i-1], pre0[i-1] + i)\n",
    "\n",
    "        if s[-1] == '0':\n",
    "            post0[-1],post1[-1] = 0,1\n",
    "        else:\n",
    "            post0[-1],post1[-1] = 1,0\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if s[i] == '0':\n",
    "                # 分析同上\n",
    "                post0[i] = min(post0[i], post0[i+1], post1[i+1] + n - i - 1)\n",
    "                post1[i] = min(post1[i], post0[i+1] + n - i) # 消耗为n - i\n",
    "            elif s[i] == '1':\n",
    "                post0[i] = min(post0[i], post1[i+1] + n - i)\n",
    "                post1[i] = min(post1[i], post1[i+1], post0[i+1] + n - i - 1)\n",
    "        \n",
    "        ans = INF \n",
    "        # 最终枚举切割点:  # 前0 | 后0 # 前1 | 后1 # 求最小值\n",
    "        for i in range(n - 1):\n",
    "            ans = min(ans, pre0[i] + post0[i+1], pre1[i] + post1[i+1])     \n",
    "        ans = min(ans, pre0[n - 1], pre1[n - 1])\n",
    "        return ans \n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        # 动态规划\n",
    "        # 设置四行dp数组\n",
    "        # pre0, pre1, post0, post1\n",
    "        # 含义分别是，包含本位置的情况下把前面变成全0/1，后面变成全0/1的成本\n",
    "        n = len(s)\n",
    "        INF = 0xffffffff\n",
    "        pre0 = [INF for _ in range(n)]\n",
    "        pre1 = [INF for _ in range(n)]\n",
    "        post0 = [INF for _ in range(n)]\n",
    "        post1 = [INF for _ in range(n)]\n",
    "\n",
    "        if s[0] == '0':\n",
    "            pre0[0],pre1[0] = 0,1\n",
    "        else:\n",
    "            pre0[0],pre1[0] = 1,0\n",
    "        for i in range(1, n):\n",
    "            if s[i] == '0':            \n",
    "                pre0[i] = min(pre0[i], pre0[i-1]) # 要么不反转，它的费用可以直接接在pre0后面\n",
    "                pre0[i] = min(pre0[i], pre1[i-1] + i) # 或者选择反转前0~i-1个1,消耗为i\n",
    "                pre1[i] = min(pre1[i], pre0[i-1] + i + 1) # 在前面全为0的基础上反转\n",
    "            elif s[i] == '1':\n",
    "                pre0[i] = min(pre0[i], pre1[i-1] + i + 1)\n",
    "                pre1[i] = min(pre1[i], pre1[i-1])\n",
    "                pre1[i] = min(pre1[i], pre0[i-1] + i)\n",
    "\n",
    "        if s[-1] == '0':\n",
    "            post0[-1],post1[-1] = 0,1\n",
    "        else:\n",
    "            post0[-1],post1[-1] = 1,0\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if s[i] == '0':\n",
    "                post0[i] = min(post0[i], post0[i+1])\n",
    "                post0[i] = min(post0[i], post1[i+1] + n - i - 1) # 消耗为n - i - 1\n",
    "                post1[i] = min(post1[i], post0[i+1] + n - i) # 消耗为n - i\n",
    "            elif s[i] == '1':\n",
    "                post0[i] = min(post0[i], post1[i+1] + n - i)\n",
    "                post1[i] = min(post1[i], post1[i+1])\n",
    "                post1[i] = min(post1[i], post0[i+1] + n - i - 1)\n",
    "        \n",
    "        ans = INF \n",
    "        # 最终枚举切割点\n",
    "        # 前0 | 后0\n",
    "        # 前1 | 后1\n",
    "        # 求最小值\n",
    "        for i in range(n):\n",
    "            if i + 1 < n:\n",
    "                ans = min(ans, pre0[i] + post0[i+1]) \n",
    "                ans = min(ans, pre1[i] + post1[i+1])\n",
    "            else:\n",
    "                ans = min(ans, pre0[i])\n",
    "                ans = min(ans, pre1[i])\n",
    "        return ans \n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:   \n",
    "        n = len(s)\n",
    "        cnt = [[0, 0] for _ in range(n)]\n",
    "        if s[-1] == \"0\":    cnt[-1][1] = 1\n",
    "        else:   cnt[-1][0] = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            cnt0, cnt1 = cnt[i+1]\n",
    "            if s[i] == \"0\":\n",
    "                cnt[i] = [min(cnt0, cnt1 + n - 1 - i), min(cnt1 + 2*(n-i) - 1, cnt0 + n - i)]\n",
    "            else:\n",
    "                cnt[i] = [min(cnt0 + 2*(n-i) - 1, cnt1 + n - i), min(cnt0 + n - 1 - i, cnt1)]\n",
    "        \n",
    "        cnt0 = cnt1 = 0\n",
    "        ans = float(inf)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if s[i] == \"0\":\n",
    "                cnt0, cnt1 = min(cnt0, cnt1 + i), min(cnt1 + 2 * i + 1, cnt0 + i + 1)\n",
    "            else:\n",
    "                cnt0, cnt1 = min(cnt1 + i + 1, cnt0 + 2 * i + 1), min(cnt0 + i, cnt1)\n",
    "            ans = min(ans, cnt[i][0] + cnt0, cnt[i][1] + cnt1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:   \n",
    "        n = len(s)\n",
    "        cnt = [[0, 0] for _ in range(n)]\n",
    "        if s[-1] == \"0\":    cnt[-1][1] = 1\n",
    "        else:   cnt[-1][0] = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            cnt0, cnt1 = cnt[i+1]\n",
    "            if s[i] == \"0\":\n",
    "                cnt[i] = [min(cnt0, cnt1 + n - 1 - i), min(cnt1 + 2*(n-i) - 1, cnt0 + n - i)]\n",
    "            else:\n",
    "                cnt[i] = [min(cnt0 + 2*(n-i) - 1, cnt1 + n - i), min(cnt0 + n - 1 - i, cnt1)]\n",
    "        \n",
    "        cnt0 = cnt1 = 0\n",
    "        ans = float(inf)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if s[i] == \"0\":\n",
    "                cnt0, cnt1 = min(cnt0, cnt1 + i), min(cnt1 + 2 * i + 1, cnt0 + i + 1)\n",
    "            else:\n",
    "                cnt0, cnt1 = min(cnt1 + i + 1, cnt0 + 2 * i + 1), min(cnt0 + i, cnt1)\n",
    "            ans = min(ans, cnt[i][0] + cnt0, cnt[i][1] + cnt1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        s1 = s[::-1]\n",
    "        lens = len(s)\n",
    "        left = [0 for i in range(lens+1)]\n",
    "        right = [0 for i in range(lens+1)]\n",
    "        \n",
    "        left[1] = 1 if s[0] == \"0\" else 0\n",
    "        right[1] = 1 if s[-1] == \"0\" else 0\n",
    "        \n",
    "        flag1 = 0\n",
    "        for i in range(1, lens):\n",
    "            if s[i] == \"1\": flag1 = i\n",
    "            \n",
    "            if s[i] == \"0\" and s[i-1] == \"0\":\n",
    "                left[i+1] = left[i] + 1\n",
    "            elif s[i] == \"0\" and s[i-1] == \"1\":\n",
    "                left[i+1] = left[i] + flag1 + i + 2\n",
    "            elif s[i] == \"1\":\n",
    "                left[i+1] = left[i]\n",
    "        \n",
    "        flag1 = 0\n",
    "        for i in range(1, lens):\n",
    "            if s1[i] == \"1\": flag1 = i\n",
    "            \n",
    "            if s1[i] == \"0\" and s1[i-1] == \"0\":\n",
    "                right[i+1] = right[i] + 1\n",
    "            elif s1[i] == \"0\" and s1[i-1] == \"1\":\n",
    "                right[i+1] = right[i] + flag1 + i + 2\n",
    "            elif s1[i] == \"1\":\n",
    "                right[i+1] = right[i]\n",
    "                \n",
    "        ans1 = [0 for i in range(lens+1)]\n",
    "        for i in range(lens+1):\n",
    "            ans1[i] = left[i] + right[lens-i]\n",
    "            \n",
    "        \n",
    "        left = [0 for i in range(lens+1)]\n",
    "        right = [0 for i in range(lens+1)]\n",
    "        \n",
    "        left[1] = 1 if s[0] == \"1\" else 0\n",
    "        right[1] = 1 if s[-1] == \"1\" else 0\n",
    "        \n",
    "        flag1 = 0\n",
    "        for i in range(1, lens):\n",
    "            if s[i] == \"0\": flag1 = i\n",
    "            \n",
    "            if s[i] == \"1\" and s[i-1] == \"1\":\n",
    "                left[i+1] = left[i] + 1\n",
    "            elif s[i] == \"1\" and s[i-1] == \"0\":\n",
    "                left[i+1] = left[i] + flag1 + i + 2\n",
    "            elif s[i] == \"0\":\n",
    "                left[i+1] = left[i]\n",
    "        \n",
    "        flag1 = 0\n",
    "        for i in range(1, lens):\n",
    "            if s1[i] == \"0\": flag1 = i\n",
    "            \n",
    "            if s1[i] == \"1\" and s1[i-1] == \"1\":\n",
    "                right[i+1] = right[i] + 1\n",
    "            elif s1[i] == \"1\" and s1[i-1] == \"0\":\n",
    "                right[i+1] = right[i] + flag1 + i + 2\n",
    "            elif s1[i] == \"0\":\n",
    "                right[i+1] = right[i] \n",
    "        ans2 = [0 for i in range(lens+1)]\n",
    "        for i in range(lens+1):\n",
    "            ans2[i] = left[i] + right[lens-i]\n",
    "            \n",
    "    \n",
    "            \n",
    "        return min(min(ans1), min(ans2))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        if len(s) == 1:\n",
    "            return 0\n",
    "        dp = [[0]*2 for _ in range(len(s))]\n",
    "        if s[0] == '1':\n",
    "            dp[0][0] = 1\n",
    "        if s[0] == '0':\n",
    "            dp[0][1] = 1 \n",
    "\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] == '1':\n",
    "                dp[i][1] = dp[i-1][1]\n",
    "                dp[i][0] = dp[i-1][1] + i + 1\n",
    "            else:\n",
    "                dp[i][1] = dp[i-1][0] + i + 1\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "        \n",
    "        dp1 = [[0]*2 for _ in range(len(s))]\n",
    "        if s[-1] == '1':\n",
    "            dp1[-1][0] = 1\n",
    "        else:\n",
    "            dp1[-1][1] = 1\n",
    "        \n",
    "        for i in range(len(s)-2,-1,-1):\n",
    "            if s[i] == '1':\n",
    "                dp1[i][1] = dp1[i+1][1]\n",
    "                dp1[i][0] = dp1[i+1][1] + len(s) - i\n",
    "            else:\n",
    "                dp1[i][0] = dp1[i+1][0]\n",
    "                dp1[i][1] = dp1[i+1][0] + len(s) - i \n",
    "        \n",
    "        res = inf\n",
    "        for i in range(len(dp)-1):\n",
    "            ans = min(dp[i][0] + dp1[i+1][0],dp[i][1] + dp1[i+1][1])\n",
    "            # print(ans)\n",
    "            res = min(res,ans)\n",
    "        # print(dp)\n",
    "        # print(dp1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = [[int(s[0]), 1 - int(s[0])]]\n",
    "        for index in range(1, len(s)):\n",
    "            char = s[index]\n",
    "            if char == '0':\n",
    "                left.append([left[-1][0], left[-1][0] + index + 1])\n",
    "            else:\n",
    "                left.append([left[-1][1] + index + 1, left[-1][1]])\n",
    "        \n",
    "        right = [[int(s[-1]), 1 - int(s[-1])]]\n",
    "        for index in range(len(s) - 2, -1, -1):\n",
    "            char = s[index]\n",
    "            if char == '0':\n",
    "                right.append([right[-1][0], right[-1][0] + len(s) - index])\n",
    "            else:\n",
    "                right.append([right[-1][1] + len(s) - index, right[-1][1]])\n",
    "        right.reverse()\n",
    "        \n",
    "        res = min(min(left[-1]), min(right[0]))\n",
    "        for cut_pos in range(len(s) - 1):\n",
    "            res = min(res, left[cut_pos][0] + right[cut_pos + 1][0], left[cut_pos][1] + right[cut_pos + 1][1])\n",
    "        \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
